P-NP Theory


Question 1
The problem 3-SAT and 2-SAT are
A
both in P
B
both NP complete
C
NP -complete and in P respectively
D
undecidable and NP complete respectively
ISRO CSE 2017   Algorithm
Question 2
Language L_{1} is polynomial time reducible to language L_{2}. Language L_{3} is polynomial time reducible to L_{2}, which in turn is polynomial time reducible to language L_{4}. Which of the following is/are true?
I. if L_{4} \in P, then L_{2} \in P
II. if L_{1} \in P or L_{3} \in P, then L_{2} \in P
III. L_{1} \in P, if and only if L_{3} \in P
IV. if L_{4} \in P, then L_{1} \in P and L_{3} \in P
A
II only
B
III only
C
I and IV only
D
I only
GATE CSE 2015 SET-3   Algorithm


Question 3
Consider two decision problems Q1,Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?
A
Q1 is in NP, Q2 is NP hard.
B
Q2 is in NP, Q1 is NP hard
C
Both Q1 and Q2 are in NP .
D
Both Q1 and Q2 are NP hard
GATE CSE 2015 SET-2   Algorithm
Question 4
Consider the decision problem 2CNFSAT defined as follows:
{ \phi | \phi is a satisfiable propositional formula in CNF with at most two literal per clause}
For example, \phi =(x_{1} \vee x_{2}) \wedge (x_{1} \vee \bar{x_{3}}) \wedge (x_{2} \vee x_{4}) is a Boolean formula and it is in 2CNFSAT.
The decision problem 2CNFSAT is
A
NP-Complete
B
solvable in polynomial time by reduction to directed graph reachability.
C
solvable in constant time since any input instance is satisfiable
D
NP-hard, but not NP-complete
GATE CSE 2014 SET-3   Algorithm
Question 5
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
A
A
B
B
C
C
D
D
GATE CSE 2014 SET-1   Algorithm


There are 5 questions to complete.

Leave a Comment