1,174 views
0 votes
0 votes
Are p and np languages all recursive? Because p and np both correspond to languages which have algorithms and algorithms means that there is a halting turning machine(either ntm or dtm). So np and p both should be recursive. Am i right here? Please answer

2 Answers

Best answer
5 votes
5 votes

First of all when it comes to "problems" you should use decidable -- recursive for corresponding language and semi-decidable -- recursively enumerable for corresponding language. 

Now, lets see the definitions of P, NP and NPC

  • P - set of problems solvable in polynomial time by a deterministic TM
  • NP - set of problems solvable in polynomial time by a non-deterministic TM
  • NPC - a subset of NP where the problems are also NP-hard

In all the definitions above, the problems must be "decidable" - who (which machine) decides it is the difference. 

https://gatecse.in/p-np-np-complete-np-hard/

selected by
3 votes
3 votes

This picture tells more about the relation between P-NP problems with REC-RE problem

  • NP-Complete,NP , P problems are subset of REC and RE set.
  • NPC is subset of REC and RE set, though NP hard may be related to or not even related to REC and RE languages
  • See the  link
  • In 𝑁𝑃 (take any 𝑁𝑃-complete problem as an example)
  • Not in 𝑁𝑃 but in 𝑅 (see the second link)
  • Not in 𝑁𝑃 and not 𝑅 (eg. the halting problem)
  • Not even in 𝑅𝐸 (eg. the complement of the halting problem)

 

edited by

Related questions

1 votes
1 votes
1 answer
1
Rhythm asked Apr 20, 2019
1,081 views
What will be the answer to this question? L’ is the complement of language L belongs to NP does not always imply thatL’ belongs to NPL’ belongs to P both a and b
1 votes
1 votes
1 answer
2
Rhythm asked Apr 18, 2019
1,836 views
Are p and np problems both closed under union intersection and concatenation and kleene closure? If yes then how?
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4