Consider the following statements. I. The complement of every Turing decidable…
2015
Consider the following statements.
I. The complement of every Turing decidable language is Turing decidable
II. There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable
Which of the above statements is/are true?
- A.
Only II
- B.
Only III
- C.
Only I and II
- D.
Only I and III
Attempted by 109 students.
Show answer & explanation
Correct answer: D
Key facts: decidable languages are closed under complement, and every NP language is decided by a nondeterministic TM that always halts.
Statement I is true: if a Turing machine decides L (it halts on all inputs), flipping accept/reject gives a machine that decides the complement of L.
Statement III is true: every language in NP has a nondeterministic polynomial-time decider, which always halts; therefore NP languages are Turing decidable.
Statement II is false: it claims an NP language can be undecidable, contradicting the fact that NP ⊆ decidable.
Conclusion: Statements I and III are true, and Statement II is false.
A video solution is available for this question — log in and enroll to watch it.