Is it required that a NP-hard problem must be computable?
I don't think so, but I am not sure.
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$:
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.
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:
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.)
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
problem()
function we can call.
$\endgroup$
Nov 8, 2016 at 5:33
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$.
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$$
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'''<...$