1
GATE CSE 2009
MCQ (Single Correct Answer)
+1
-0.3
Let $${\pi _A}$$ be a problem that belongs to the class NP. Then which one of the following is TRUE?
A
There is no polynomial time algorithm for $${\pi _A}$$
B
If $${\pi _A}$$ can be solved deterministically in polynomial time, then P = NP
C
If $${\pi _A}$$ is NP-hard, then it is NP-complete.
D
$${\pi _A}$$ may be undecidable.
2
GATE CSE 2006
MCQ (Single Correct Answer)
+1
-0.3
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
A
R is NP-complete
B
R is NP-hard
C
Q is NP-complete
D
Q is NP-hard
3
GATE CSE 2004
MCQ (Single Correct Answer)
+1
-0.3
The problems 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
4
GATE CSE 2003
MCQ (Single Correct Answer)
+1
-0.3
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?
A
Π is NP-hard but not NP-complete
B
Π is in NP, but is not NP-complete
C
Π is NP-complete
D
Π is neither NP-hard, nor in NP
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP