ExamSIDE.Com

GATE CSE 2003 Question

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 2004 Question

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

GATE CSE 2006 Question

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

GATE CSE 2009 Question

Let ${\pi _A}$ be a problem that belongs to the class NP. Then which one of the following is TRUE?
There is no polynomial time algorithm for ${\pi _A}$
If ${\pi _A}$ can be solved deterministically in polynomial time, then P = NP
If ${\pi _A}$ is NP-hard, then it is NP-complete.
${\pi _A}$ may be undecidable.