48 votes 48 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 Theory of Computation gatecse-2015-set2 theory-of-computation decidability easy + – go_editor asked Feb 12, 2015 • edited Jun 15, 2018 by Milicevic3306 go_editor 16.1k views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments JashanArora commented Mar 12, 2020 reply Follow Share 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 votes 0 votes shashankrustagi commented Feb 2, 2021 reply Follow Share not in syllabus. 3 votes 3 votes Abhrajyoti00 commented Oct 18, 2022 reply Follow Share P or NP → Decidable, but converse is not True. 0 votes 0 votes Please log in or register to add a comment.
Best answer 63 votes 63 votes 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 answered Feb 26, 2015 • edited Jun 15, 2018 by Milicevic3306 Arjun comment Share Follow See all 2 Comments See all 2 2 Comments reply saurav04 commented Feb 1, 2016 reply Follow Share @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 ? 5 votes 5 votes Arjun commented Feb 1, 2016 reply Follow Share Nopes. Any NP problem is decidable- so no question of infinite loop for no cases. Non-determinism is only finite choice- not infinite. 15 votes 15 votes Please log in or register to add a comment.
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. Paras Nath answered Sep 24, 2016 Paras Nath comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes Answer: D Rajarshi Sarkar answered Feb 12, 2015 Rajarshi Sarkar comment Share Follow See all 2 Comments See all 2 2 Comments reply Snehil Joshi commented Feb 25, 2015 reply Follow Share And how does it come to be D? What about NP-Hard problems in NP area?? 0 votes 0 votes akash commented Sep 20, 2015 reply Follow Share @ Arjun sir,@jow snow i have same doubt as Snehil..What about NP-Hard problems in NP area?? 0 votes 0 votes Please log in or register to add a comment.
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. sameer2009 answered Feb 13, 2015 sameer2009 comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Snehil Joshi commented Feb 25, 2015 reply Follow Share Yeah, That's fine. But other institutes including Ace, ME, GateCse(not an institute) gave the answer as D only. IDK why..!! 0 votes 0 votes Snehil Joshi commented Feb 26, 2015 reply Follow Share NP-Hard are a part of NP ryt?? 0 votes 0 votes sameer2009 commented Feb 26, 2015 reply Follow Share 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. 4 votes 4 votes Please log in or register to add a comment.
