1 votes 1 votes I) Every language in NP is recursive. II)Every language in NP is recursively enumerable. Which of the statements is /are true? A. I only B. II only C. Both I and II D Neither I nor II Theory of Computation theory-of-computation recursive-and-recursively-enumerable-languages + – sh!va asked Jul 12, 2016 • retagged Jul 4, 2017 by Arjun sh!va 3.0k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes p⊆Np⊆recursive⊆recursive enumerable just remember this talha hashim answered Dec 12, 2018 talha hashim comment Share Follow See 1 comment See all 1 1 comment reply commenter commenter commented Jun 13, 2019 reply Follow Share NP is proper subset of recursive which is in turn a proper subset of REL. src: https://cs.stackexchange.com/questions/90659/what-is-the-relation-between-np-np-hard-problems-and-recursive-r-e-languages-an 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes i think every problem in NP is decidable means it is recursive .and every recursive problem is recursively enumerable so we can say that both are true,correct me if i am wrong .. Siddhi Viradiya answered Jul 13, 2016 Siddhi Viradiya comment Share Follow See all 5 Comments See all 5 5 Comments reply sh!va commented Jul 13, 2016 reply Follow Share yes you are right..!! answer is C 0 votes 0 votes sh!va commented Jul 13, 2016 reply Follow Share @Sidhi: Sir, I have a doubt what does "every problem in NP is decidable " means? What we are deciding for given NP problem? Are we deciding proposed solution is correct or not? Or are we deciding whether any solution exists for given problem? Sorry, if I asked a lame question :P 0 votes 0 votes Siddhi Viradiya commented Jul 14, 2016 reply Follow Share i can't understand what you want to ask exactly..may below link will help you to understand, check it out. https://www.quora.com/Theoretical-Computer-Science-Are-all-P-languages-decidable-Are-all-NP-languages-decidable 0 votes 0 votes sh!va commented Jul 14, 2016 reply Follow Share @Sidhi: thanks for that wonderful link.. Concept is pretty clear now!! NP is the class of languages that can be recognized by a non deterministic Turing machine A decidable language is a formal language for which there exists a Turing machine which will, when presented with any finite input string , halt and accept if the string is in the language, and halt and reject otherwise. Since any language in NP can be recognized by a non deterministic TM, there is a TM that always halts when presented with any finite input string of the language. Hence NP is decidable Since P⊂ NPP⊂ NP, any language in P is also decidable. 1 votes 1 votes talha hashim commented Dec 12, 2018 reply Follow Share p⊆Np⊆recursive 0 votes 0 votes Please log in or register to add a comment.