1
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
2
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
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
CBSE
Class 12