Is every NP-hard problem computable?

Problem Detail: 

Is it required that a NP-hard problem must be computable?

I don't think so, but I am not sure.

Asked By : Kevin Meier

Answered By : jmite

No, an $NP$-hard problem need not be computable. The definition is fairly complete: a problem $L$ is $NP$-hard if that problem having a poly-time solution implies every problem in $NP$ has a poly-time solution (that is, a reduction to $L$ exists for every problem in $NP$.).

Uncomputable problems are then vacuously hard: suppose we could solve one in polynomial time. Then we use the proof that it's uncomputable to derive that it's both computable and uncomputable, a contradiction. From this falsehood, we can derive anything, namely that there is a polynomial time algorithm for whatever $NP$ problem we are looking at.

For example, consider the halting problem $H$. We can reduce any $NP$ language $A$ to $H$ as follows, assuming we have a polytime checker $f(s,c)$ which checks if $c$ is a certificate for $s\in A$:

• Given input $s$
• Construct (but don't run) Turing Machine $M$ which takes input $x$ tries every certificate $c$ and halts if $c$ is a certificate verifying that $s\in A$.
• Return $H(M,x)$ (that is, return true iff $M$ halts on input $x$)

Thus, with a single call to a poly-time algorithm solving the Halting Problem, we can solve any $NP$ problem in polynomial time.

Such a reduction is not useful, because all it does is tells if "if false then something". We already know that there's no polytime algorithm for uncomputable problems.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65655