3
$\begingroup$

So i came upon this thread :

https://gateoverflow.in/57631/relation-between-np-recursive-and-recusive-enumerable

and the guy says Every language in NP is recursive and Every language in NP is recursively enumerable.

but i dont get it, isn't NP the set of problems which we can only determine if a given answer is true in polynomial? doesn't that mean if the answer is no we may not know?

So i'm kinda confused here and really can't put all these together

so overall my question is : can someone please tell me what is the relation between NP/NP-hard/NP-complete problems and Recursive/RE languages ?

i read about these stuff in different courses but non of them combined all of them together for a bigger picture

(also i know that Recursive languages are a subset of RE)

also based on this : https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard

NP should not be recursive because NP is set of problems which IF the answer is yes we can detect it in polynomial, but that thread doesn't say anything about what happens if its not NP

$\endgroup$
2
$\begingroup$

Overall: $NP\text{-complete} \subseteq NP \subsetneq R \subsetneq RE$

$NP\text{-complete} \subseteq NP$ by definition. It is unknown whether or not there are problems in $NP$ that are not $NP\text{-complete}$.

$NP \subseteq R$ as explained in Yuval Filmus's answer. The subset relation is strict ($NP \subsetneq R$) because we know there are problems in $R$ that are not in $NP$.

Since every $NP$ problem is in $R$ and as you pointed out $R$ is a subset of $RE$, $NP \subsetneq RE$ as well.

$NP\text{-hard}$ problems are at least as hard as the hardest problems in $NP$ but there's no upper limit on how hard they themselves can be. There are $NP\text{-hard}$ problems that are:

  • In $NP$ (take any $NP\text{-complete}$ problem as an example)
  • Not in $NP$ but in $R$ (see the second link)
  • Not in $NP$ and not $R$ (eg. the halting problem)
  • Not even in $RE$ (eg. the complement of the halting problem)

Putting this all together, you can visualize these classes in a Venn diagram like so:

Venn diagram containing P, NP, NP-hard, NPC, R, and RE

(If $P = NP$, then the innermost region would be a single circle representing $P = NP = NP\text{-complete}$)

$\endgroup$
4
$\begingroup$

Every problem in NP can be decided in exponential time (and so it is recursive). Recall that one of the definitions of NP goes via witnesses:

A language $L$ is in NP if there is a polynomial $P$ and a predicate $f$ computable in polynomial time such that $x \in L$ if and only if there exists a "witness" $y$ of length at most $P(|x|)$ such that $f(x,y) = \mathrm{True}$.

(A predicate is a function which returns True or False.)

Let's suppose that $y$ is in binary. Given an input $x$, in time $2^{P(|x|)}$ we can go over all potential witnesses $y$, and for each of them calculate $f(x,y)$. If $f(x,y) = \mathrm{True}$ for any of them, then $x$ is in $L$, and otherwise $x$ is not in $L$.

$\endgroup$
  • $\begingroup$ Thanks for the answer, So what about NP-hard problems? any relation between NP hard and R.E or Recursive languages? ( i guess Np-complete is also recursive since its a subset of NP) $\endgroup$ – John P Apr 14 '18 at 18:20
  • $\begingroup$ NP-hard problems could be recursive, not recursive but recursively enumerable, or not even recursively enumerable. $\endgroup$ – Yuval Filmus Apr 14 '18 at 19:11
  • $\begingroup$ So we still do not know the relation between NP-hard and recursively enumerable languages but we do know that it is not recursive, correct? $\endgroup$ – John P Apr 15 '18 at 3:35
  • 1
    $\begingroup$ On the contrary, we know that all of these possibilities can occur. $\endgroup$ – Yuval Filmus Apr 15 '18 at 4:47
  • 1
    $\begingroup$ No Turing machine decides the halting problem, since it is not recursive. $\endgroup$ – Yuval Filmus Apr 16 '18 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.