ExamSIDE.Com

© ExamSIDE.Com 2019

About Us Privacy Policy

GATE CSE 2003 Question

Signle Correct Answer
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

Signle Correct Answer
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

Signle Correct Answer
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

Signle Correct Answer
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.

Share