edited by
15,315 views
48 votes
48 votes

Consider the following statements.

  1. The complement of every Turing decidable language is Turing decidable
  2. There exists some language which is in NP but is not Turing decidable
  3. If L is a language in NP, L is Turing decidable

Which of the above statements is/are true?

  1. Only II
  2. Only III
  3. Only I and II
  4. Only I and III
edited by

7 Answers

Best answer
63 votes
63 votes
  1. is true. The solution to a decision problem is either "yes" or "no", and hence if we can decide a problem, we have also decided its complement-  just reverse "yes" and "no". (This is applicable for decidability and not for acceptance)
     
  2. is false. Because NP class is defined as the class of languages that can be solved in polynomial time by a non-deterministic Turing machine. So, none of the NP class problems is undecidable.
     
  3. is true for same reason as II.

So, answer is D.

edited by
3 votes
3 votes
Answer: D
2 votes
2 votes
Ans: Option D.

There exists some language which is in NP but is not Turing decidable. Such languages may be NP-Hard. So cannot be Option B.
Answer:

Related questions

26 votes
26 votes
5 answers
4
go_editor asked Feb 12, 2015
14,096 views
Consider the following routing table at an IP router:$$\begin{array}{|l|l|l|} \hline \textbf {Network No} & \textbf {Net Mask} & \textbf{Next Hop} \\\hline \text {128.96...