1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.