I would like to know if there exists an NP-hard language which is also a member of co-RE\R? I think it depends if P=NP or not, but i'm not sure.
Can I simply assume NP-hard is in R?
Can you direct me how to think about it?
$\begingroup$
$\endgroup$
0
Add a comment
|
$\begingroup$
$\endgroup$
0
There are NP-hard languages arbitrarily high in the arithmetical hierarchy.
To answer your specific question, the complement of the halting problem is NP-hard and it's in $\mathrm{coRE}\setminus\mathrm{R}$. To see this, let $M$ be a Turing machine that tries all variable assignments for a $\mathrm{SAT}$ instance. Let it loop forever if it finds a satisfying assignment and let it halt if it doesn't, or if the input isn't a valid encoding of a $\mathrm{SAT}$ instance. Now, for any string $x$, $x\in\mathrm{SAT}$ iff $\langle M\rangle,x\in\overline{\mathrm{HALT}}$ so we have a reduction from $\mathrm{SAT}$ to the complement of the halting problem.
answered Jul 10 '17 at 16:58
