patternModerate
Is every NP-hard problem computable?
Viewed 0 times
computablehardeveryproblem
Problem
Is it required that a NP-hard problem must be computable?
I don't think so, but I am not sure.
I don't think so, but I am not sure.
Solution
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$,
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$,
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.)
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:
- The definitions leave open the possibility that non-computable functions might be NP-hard. Are there actually non-computable, NP-hard functions?
- 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.)
Context
StackExchange Computer Science Q#65655, answer score: 18
Revisions (0)
No revisions yet.