Consider the following statements: 1. The complement of every Turning decidable language is Turning 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?


Consider the following statements:

1. The complement of every Turning decidable 
   language is Turning 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?

 A
Only 2
B
Only 3
C
Only 1 and 2
 D
Only 1 and 3

Explanation:

1 is true: Complement of Turing decidable is Turing Decidable.

3 is true. All NP problems are Turing decidable 
   (See http://www.geeksforgeeks.org/np-completeness-set-1/)

2 is false:  The definition of NP itself says solvable in 
     polynomial time using non-deterministic Turing machine.

Leave a comment

Your email address will not be published. Required fields are marked *