GATE 2012 CS (CS1) – Question 14

Theory of Computation · Turing Machines and Undecidability · 1 mark · Multiple choice

Assuming P≠NP, which is true?

NP-complete = NP
$\mathrm{NP\!\!\!-complete}\cap P=\varnothing$
NP-hard = NP
P = NP-complete

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\mathrm{NP\!\!\!-complete}\cap P=\varnothing$

Explanation

If an NP-complete problem were in P, every NP problem could reduce to it in polynomial time and would also be in P. This contradicts P≠NP. Thus no NP-complete problem belongs to P, and the intersection is empty, B.

More Turing Machines and Undecidability questions

GATE 2012 CS (CS1) Q34 – Which problems are decidable? 1: Does an arbitrary program ever output anything? 2: Given…
GATE 2013 CS (CS1) Q27 – Which are false? 1: Every nondeterministic TM has an equivalent deterministic TM. 2:…
GATE 2013 CS (CS1) Q28 – Which are true? 1: Undirected cycle detection is in P. 2: Undirected cycle detection is in…
GATE 2013 CS (CS1) Q51 – Which problems are undecidable? 1: Given CFG G, is L(G)=∅? 2: Given CFG G, is L(G)=Σ*? 3:…
GATE 2011 CS (CS1) Q18 – Which pair has different expressive power?
GATE 2010 CS (CS1) Q27 – L₁ is recursive. L₂,L₃ are recursively enumerable but nonrecursive. Which is NOT…

All Turing Machines and Undecidability questions →