GATE 2013 CS (CS1) – Question 28

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

Which are true? 1: Undirected cycle detection is in P. 2: Undirected cycle detection is in NP. 3: Every NP-complete problem has a nondeterministic polynomial-time algorithm.

1,2,3
1,2 only
2,3 only
1,3 only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) 1,2,3

Explanation

DFS detects an undirected cycle in linear graph time, so the decision problem is in P and therefore also in NP. By definition NP-complete problems belong to NP, which supplies a nondeterministic polynomial-time algorithm. All three statements hold, A.

More Turing Machines and Undecidability questions

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…
GATE 2015 CS (CS2) Q20 – Which statements are true? I: The complement of every Turing-decidable language is…
GATE 2021 CS (CS2) Q46 – S1: Every infinite regular language has an undecidable language as a subset. S2: Every…
GATE 2026 CS (CS2) Q13 – Which one of the following statements is equivalent to the assertion: Turing machine M…

All Turing Machines and Undecidability questions →