+1 vote
896 views

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

retagged | 896 views

p⊆Np⊆recursive⊆recursive enumerable

just remember this
by Loyal (5.6k points)
0
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 ..
by (181 points)
0
yes you are right..!!

0

@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

https://www.quora.com/Theoretical-Computer-Science-Are-all-P-languages-decidable-Are-all-NP-languages-decidable
+1

@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.
0
p⊆Np⊆recursive