19
$\begingroup$

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

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

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ "The definition is fairly complete", but is not what follows that quote in your answer. ​ ​ $\endgroup$ – user12859 Nov 7 '16 at 0:02
  • $\begingroup$ I have a question about this. I can imagine a function that solves the halting problem for the largest set of programs possible under some appropriate constraints, but I can imagine this function still not being computable (in the sense that we would never find it even given an infinite amount of time). Yet if we somehow did have the solution to it, it's not even clear to me that it should solve all NP-hard problems necessarily. So either the logic in this answer doesn't follow (meaning undecidable != uncomputable), or my reasoning is flawed (likely). So what is the flaw? $\endgroup$ – Mehrdad Nov 7 '16 at 1:27
  • 12
    $\begingroup$ Most of this answer is incorrect, including your definition of NP hard: problem A is NP hard if, "for every NP problem B, there is a poly-time reduction of B to A." That is not the same thing as "if A is poly-time, then P = NP." (The latter is a consequence of the former, but not vice versa.) In particular, there are almost certainly non-computable problems that also fail to be NP hard. I haven't worked out the details, but problem of membership in a sufficiently generic set (in the sense of forcing) should do the trick. The halting set, specifically, is NP-hard, however, by your reduction. $\endgroup$ – Mike Haskel Nov 7 '16 at 4:35
  • 7
    $\begingroup$ Think about a poly-time reduction from A to B like this: it is a program that runs in polynomial time, but it has the special ability to query, in a single step, an oracle that answers instances of problem B. Regardless of whether there is a poly-time algorithm for B, or even whether B is computable, it still makes sense to ask the following question: assuming that the oracle correctly answers the questions asked of it (in a single step), does the program in question run in polynomial time and correctly solve instances of problem A? $\endgroup$ – Mike Haskel Nov 7 '16 at 4:41
  • 2
    $\begingroup$ @MikeHaskel Your oracle analogy is only accurate if, after querying the oracle, the program must stop with the same answer as that oracle. Otherwise, co-SAT reduces to SAT: query the oracle and negate. In some reduction notions e.g. Turing reduction, this would be acceptable, but in standard poly-time reduction, or even in many-one reduction, it is not. $\endgroup$ – chi Nov 7 '16 at 20:18
16
$\begingroup$

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.)

$\endgroup$
  • 2
    $\begingroup$ Can't you construct an undecidable language which isn't NP-hard by diagonalization? Diagonalize against all deciders and all polytime reductions from SAT. $\endgroup$ – Yuval Filmus Nov 7 '16 at 23:22
  • 1
    $\begingroup$ @YuvalFilmus That probably works, yeah. I think writing out the details for why diagonalizing against polytime reductions from SAT is possible amounts is similar in flavor to showing that forcing works, though, so I didn't think about it in those terms. $\endgroup$ – Mike Haskel Nov 8 '16 at 1:26
  • 1
    $\begingroup$ @YuvalFilmus I also added the clarification just now that you have to assume P $\neq$ NP: there was definitely a step in my proof that read "take some problem in NP but not in P." $\endgroup$ – Mike Haskel Nov 8 '16 at 1:28
  • 1
    $\begingroup$ @aelguindy I'm not sure what the most accessible method to prove it is. I mentioned the technique of forcing, which is very general and powerful. I learned it from people, not textbooks, so I don't personally know of a great reference on forcing. As Yuval pointed out, however, forcing is probably overkill: some more direct argument involving diagonalization probably works. Soare's "Recursively Enumerable Sets and Degrees" is a textbook that covers a lot of that style of argument if you want to become familiar with it. Again, most of it is probably overkill, though. ... $\endgroup$ – Mike Haskel Nov 8 '16 at 1:45
  • 1
    $\begingroup$ @aelguindy Also, if you think of the set of of decision problems as a topological space, you can probably massage the Baire Category theorem to produce a proof. This theorem is closely related to forcing, but is older and more straightforward. $\endgroup$ – Mike Haskel Nov 8 '16 at 1:46
10
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ Note that, while some non-computable problems (like the halting problem) are NP-hard, that does not mean that all non-computable problems are NP-hard. See my comments on jmite's answer. NP-hardness is a positive property: it says that answers to your problem can help solve NP problems. Being NP-hard implies that the problem is, to some degree, difficult. Not all difficult problems are NP-hard. $\endgroup$ – Mike Haskel Nov 7 '16 at 4:45
  • $\begingroup$ @MikeHaskel: Possessing the solution to the halting problem reduces all problems to P * difficulty of the halting problem.. $\endgroup$ – Joshua Nov 7 '16 at 17:05
  • 1
    $\begingroup$ @Joshua: That makes no sense. It's like a fragment of a non-proof. What do you even mean for a problem to have a finite number of bits in its solution, and why do you think this applies to all uncomputable problems? What do you mean by "P * halts"? What's the rest of "reduce via the nth bit of ..."? $\endgroup$ – user2357112 supports Monica Nov 7 '16 at 20:36
  • 1
    $\begingroup$ @Joshua: Looks like the core issue is that you're assuming that every problem corresponds to a Turing machine. Not every problem corresponds to a Turing machine. There's no problem() function we can call. $\endgroup$ – user2357112 supports Monica Nov 8 '16 at 5:33
  • 1
    $\begingroup$ You should probably move this to chat or something $\endgroup$ – Destructible Lemon Nov 8 '16 at 5:37
10
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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$$

$\endgroup$
3
$\begingroup$

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'''<...$

$\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.