Is every NP-hard problem computable?

Question

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

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

Answer 1

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.

Answer 2

There appears to be some considerable confusion in this community regarding this question. I'll give a detailed answer in the hope of clearing up the water and illuminating the relationship between computability and NP-hardness.

First, I believe that being clear and explicit about the various definitions involved will resolve a lot of the confusion.

A string is a finite sequence of characters from some fixed finite alphabet.

A decision problem is a set of strings. (This set is typically infinite.) Think of the decision problem as testing strings for some property: the strings with the property are in the set, and the strings without the property are not.

Assume we have two decision problems, $A$ and $B$. Say $A$ is polynomial-time reducible to $B$ if there is some polynomial $p(x)$ and algorithm some algorithm $M$ such that, for all strings $s$,

• If you provide $M$ with input $s$, $M$ halts in fewer than $p(|s|)$ steps (where $|s|$ is the length of the string $s$) and outputs a string $M(s)$.
• $s$ is in $A$ if and only if $M(s)$ is in $B$.

A decision problem $B$ is NP-hard if, for every NP decision problem $A$, $A$ is polynomial-time reducible to $B$.

A decision problem is computable if there is an algorithm $M$, that, for all strings $s$,

• If you provide $M$ with input $s$, $M$ halts and outputs either "yes" or "no".
• The output is "yes" if $s$ is in $A$ and "no" otherwise.

With the above definitions, we can immediately clarify what I think might be the root confusion in your question: nothing in the definitions of decision problem, reductions, or NP-hardness requires the decision problems to be computable. The definitions make perfect sense thinking of decisions problems as arbitrary sets of strings, and these sets can be very nasty indeed.

---

That leaves two questions on the table:

1. The definitions leave open the possibility that non-computable functions might be NP-hard. Are there actually non-computable, NP-hard functions?
2. There is an intuition that saying a problem is NP-hard is saying that it is hard to solve. Saying that it is non-computable is like saying it's "really hard" to solve. So, are all non-computable problems NP-hard?

---

Question 1 is easier to answer. There are two particularly important ways to find non-computable decision problems that are NP-hard. The first is the halting problem: the halting problem, $H$, has the property that every computable decision problem is polynomial-time reducible to $H$. Since NP problems are computable, every NP problem is polynomial-time reducible to $H$, so $H$ is NP-hard.

The other important way to build a non-computable, NP-hard problem is to observe that we can combine any known NP-hard problem with any known non-computable problem. Let $A$ be NP-hard and $B$ be non-computable. Form the decision problem $A \oplus B$ as follows: $A \oplus B$ contains those strings of the form "0, followed by a string in $A$" and those of the form "1, followed by a string in $B$". $A \oplus B$ is NP-hard because we can turn any reduction (of any problem) to $A$ into a reduction to $A \oplus B$: just tweak the algorithm to output an extra "0" at the front of its output string. $A \oplus B$ is non-computable, since computing $A \oplus B$ requires deciding which strings that start with "1" are in the set; this is impossible, since $B$ is non-computable.

---

Question 2 is considerably tricker, but in fact there are non-computable decision problems that are not NP-hard (assuming P $\neq$ NP). Yuval's fine answer constructs such a decision problem explicitly. (For any computability theorists in the room, any "Cohen $\Pi^0_1$-generic" will do the trick, as well.) I'll break down why the intuition that "NP-hard problems are hard, non-computable problems are harder" is wrong.

NP-hardness and non-computability both say that a problem is "hard" in a very general sense, but they are very different and shouldn't be lumped together as the same kind of phenomenon. Specifically, NP-hardness is a "positive" property: an NP-hard problem $A$ is hard in the sense that, given access to a cheat sheet for $A$, you can solve a hard class of problems. On the other hand, non-computability is a "negative" property: a non-computable problem $A$ hard in the sense that you cannot solve $A$ with a given class of resources.

("Forcing," by the way, is the technique used to produce the "Cohen $\Pi^0_1$ generic" that I mentioned. To be very very vague, forcing is a general way to produce things that are "generic" in that they have no positive properties and every negative property. That's why forcing can directly produce a problem that's neither computable nor NP-hard.)

Answer 3

Nope. NP-Hard means it is as hard, or harder, than the hardest NP-problems. Intuitively, being uncomputable will make it a lot more difficult than NP.

Wikipedia:

There are decision problems that are NP-hard but not NP-complete, for example the halting problem.

Everyone knows that is not computable

Answer 4

For completeness, let us prove the following theorem:

There exists an uncomputable language which is not NP-hard if and only if P$\neq$NP.

If P=NP then any non-trivial language (one which differs from $\emptyset,\{0,1\}^*$) is NP-hard (exercise), and in particular any uncomputable language is NP-hard.

Now suppose that P$\neq$NP. Let $T_i$ be some enumeration of all Turing machines. We will construct the required language $L$ in stages. At each stage we will keep a $\{0,1,?\}$ coloring of $\{0,1\}^*$ which we also denote by $L$; here $0$ means that we have decided that the string is not in $L$, $1$ means that we have decided that the string is in $L$, and $?$ means that we haven't decided yet. All but finitely many strings will be colored $?$.

In step $2i$, we think of $T_i$ as a machine which either accepts its input, rejects it, or never halts. If $T_i$ doesn't always halt then we don't do anything. If $T_i$ always halts then we find a string $x$ such that $L(x) = ?$, and set $L(x) := 0$ if $T_i(x)$ accepts and $L(x) := 1$ if $T_i(x)$ rejects.

In step $2i+1$, we think of $T_i$ as a machine computing a (possibly) partial function on its input. If $T_i$ isn't total, or if it is total but doesn't run in polynomial time, or if it is total but its range is finite, we don't do anything. If $T_i$ is total, runs in polynomial time, and has infinite range, then we find a string $x$ such that $L(T_i(x)) = ?$. If $x \in \mathrm{SAT}$ (that is, if $x$ encodes a satisfiable CNF) then we set $L(x) := 0$, and otherwise we set $L(x) := 1$.

After infinitely many steps, we get a $\{0,1,?\}$ coloring of $\{0,1\}^*$ which we complete to an actual language in an arbitrary way.

The resulting language $L$ isn't computable: step $2i$ ensures that $T_i$ doesn't compute it. It also isn't NP-hard, but here the reasoning is a bit more delicate. Suppose that $T_i$ is a polytime reduction from SAT to $L$. If the range of $T_i$ is finite then we can turn $T_i$ into a polytime machine deciding SAT, by listing the truth table of $L$ on the range of $T_i$. This is impossible by the assumption P$\neq$NP. Thus $T_i$ has infinite range, but then step $2i+1$ rules out its being a reduction from SAT to $L$.

Answer 5

A language $L$ is NP-hard if for every $L' \in \mathrm{NP}$ we have that $L'$ is polynomial-time reducible to $L$. The acceptance problem for nondeterministic Turing machines

$$ A_{\mathsf{NTM}} = \{ \langle M,w \rangle \mid M \text{ is a nondeterministic Turing machine that accepts } w \}$$

is undecidable and is NP-hard. For consider an $L' \in \mathrm{NP}$. $L'$ is decided by some nondeterministic Turing machine $M'$ with polynomial time complexity. A poly-time reduction $f$ from $L'$ to $A_{\mathsf{NTM}}$ is given by

$$f(x) = \langle M,x \rangle$$

Answer 6

I think what causes people to think there is no uncomputable NP-hard problem is that they miss the point that NP-hardness is a lower bound on the hardness of a problem, not an upper bound on their hardness like P or NP.

A language L being NP-hard means that it is above language in NP and that is. Now if you understand this what need is to show that there are arbitrary harder problem.

Let $A$ be a language. Consider algorithms augmented with a black-box that they can use to deciding membership in $A$. Let's denote them by $\mathsf{C}^A$. It is easy to see that the halting problem for $\mathsf{C}^A$, $Halt_{\mathsf{C}^A}$ is not in $\mathsf{C}^A$.

In computablity theory this is called jump of $A$ and is denoted by $A'$. So $A < A'$ strictly. And nothing stops us from repeating this: $A<A'<A''<A'''<...$