GATE 2015 CS (CS2) – Question 20
Which statements are true?
I: The complement of every Turing-decidable language is Turing-decidable.
II: Some language in NP is not Turing-decidable.
III: Every language in NP is Turing-decidable.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) I and III only
Explanation
A decider always halts, so exchanging its accepting and rejecting outcomes decides the complement, proving I. An NP verifier has polynomially bounded witnesses; enumerate all such witnesses and test them, a finite decision procedure. Thus III holds and II is false. Answer D.