ExamSIDE
Questions (Powered by ExamGOAL)
Algorithms
Complexity Analysis and Asymptotic Notations
Marks 1Marks 2
Searching and Sorting
Marks 1Marks 2
Divide and Conquer Method
Marks 1Marks 2
Greedy Method
Marks 1Marks 2
P and NP Concepts
Marks 1Marks 2
Dynamic Programming
Marks 1Marks 2
Previous
1
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
Previous
Questions Asked from Marks 1
GATE CSE 2015 Set 2 (1) GATE CSE 2013 (1) GATE CSE 2009 (1) GATE CSE 2006 (1) GATE CSE 2004 (1) GATE CSE 2003 (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