rahulkala Complement of NPC can be in co-NP at max — still decidable.

Any language L that is the complement of an NP-complete language is co-NP-complete

https://www.cl.cam.ac.uk/teaching/0910/Complexity/lecture9.pdf

Dark Mode

11,410 views

47 votes

Consider the following statements.

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

Which of the above statements is/are true?

- Only II
- Only III
- Only I and II
- Only I and III

rahulkala Complement of NPC can be in co-NP at max — still decidable.

Any language L that is the complement of an NP-complete language is co-NP-complete

https://www.cl.cam.ac.uk/teaching/0910/Complexity/lecture9.pdf

0

62 votes

Best answer

- 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)

- 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.

- is true for same reason as II.

So, answer is **D**.

@Arjun sir if "NP is class of language that can be solved in polynomial time by Non deterministic turing machine "then these language will surely halt if string belong to language and if does not belong to language then it may fall into loop or reject (because it is simulating by NTM),Now A problem is decidable if there is a Algorithm for which works for YES case as well as NO case ...I am confused that if a language belong to NP then it can handle yes case but NO case it may fall into loop ..... So how does it make NP class pb decidable ?

4

9 votes

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.