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?
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?
3
GATE CSE 2004
MCQ (Single Correct Answer)
+1
-0.3
The problems 3-SAT and 2-SAT are
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 ?
Questions Asked from Marks 1
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization