in Theory of Computation edited by
11,410 views
47 votes
47 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
in Theory of Computation edited by
11.4k views

4 Comments

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
0
not in syllabus.
1
1
P or NP → Decidable, but converse is not True.
0
0

7 Answers

62 votes
62 votes
Best answer
  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
by

2 Comments

@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
4
Nopes. Any NP problem is decidable- so no question of infinite loop for no cases. Non-determinism is only finite choice- not infinite.
14
14
9 votes
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.
3 votes
3 votes
Answer: D

2 Comments

And how does it come to be D? What about NP-Hard problems in NP area??
0
0

@ Arjun sir,@jow snow

i have same doubt as Snehil..What about NP-Hard problems in NP area??

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

4 Comments

Yeah, That's fine.
But other institutes including Ace, ME, GateCse(not an institute) gave the answer as D only. IDK why..!!
0
0
NP-Hard are a part of NP ryt??
0
0
NP-Hard is atleast as hard as hardest problem in class NP.

All problems in NP are reducible to NP-Hard.

NP-Hard may or may not belong to class NP.

If a problem Z is NP-Hard and it belongs to NP then Z is NP-Complete which is decidable using nondeterministic polynomial time turing machine.
3
3
Answer:

Related questions