What is the relation between NP/NP-hard problems and Recursive/R.E languages? any of them a subset of another?

Question

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

Answer 1

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:

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

Answer 2

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