GATE CSE 2003
MCQ (Single 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 ?
Questions Asked from P and NP Concepts (Marks 1)
Number in Brackets after Paper Indicates No. of Questions
GATE CSE Subjects
Theory of Computation
Database Management System