Log In
1 vote

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

in Theory of Computation
retagged by

2 Answers

2 votes
p⊆Np⊆recursive⊆recursive enumerable

just remember this
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 ..
yes you are right..!!

answer is C

@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

i can't understand what you want to ask exactly..may below link will help you to understand, check it out.

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

Related questions

0 votes
1 answer
If a language L and its complement L' are recursively enumerable then choose the correct statement a) L is recursive but not L' b) Both L and L' are recursive c) L' is recursive but not in L d) None of these
asked Aug 22, 2017 in Theory of Computation Anshul Shankar 534 views
0 votes
1 answer
consider the following problems p1: {<M,x,k>| M is a Turing machine M does not halt on x within k steps } p2:{<M>|M is a Turing machine and M accepts at least two strings of different length} p3:{<M>| M is a Turing machine and there exists an input whose length is less than 100 on which M halts } the problems which are RE but not REC?
asked Dec 24, 2018 in Theory of Computation suneetha 348 views
0 votes
2 answers