Is there an undecidable problem which is not NP-hard?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ The title implies a very different kind of question from the actual post. $\endgroup$– Vijay DJan 1, 2013 at 9:32
-
$\begingroup$ How so? I think they are identical. Perhaps you are referring to a previous title? $\endgroup$– Yuval FilmusJan 2, 2013 at 1:27
-
$\begingroup$ @Yuval, I think Vijay refers to the title before it was edited. $\endgroup$– KavehJan 3, 2013 at 7:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
7
If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$\neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.
We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.
The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s \in SAT$ iff $f_i(s) \notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s \in A$ iff $|s| \in K$.
By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n \in K$ (for $n \geq 2$) by taking a majority of three strings of length $n$.
answered Jan 1, 2013 at 7:41
-
3$\begingroup$ If P=NP then a polytime reduction can solve any NP problem. $\endgroup$ Jan 1, 2013 at 13:36
-
1$\begingroup$ The set $\{ f_i(\phi) \}$ is infinite, where $\phi$ ranges over all SAT instances. $\endgroup$ Jun 29, 2020 at 16:28
-
2$\begingroup$ How would you construct such an enumeration $f_i$? I doubt that this is possible. $\endgroup$ Mar 31, 2021 at 8:56
-
1$\begingroup$ There's a standard trick. You enumerate all pairs of $(T,p)$, where $T$ is a Turing machine and $p$ is a polynomial. You associate each such pair with a function $f(x)$ which consists of running $T(x)$ for $p(|x|)$ steps. $\endgroup$ Mar 31, 2021 at 8:57
-
1$\begingroup$ IIUC, this proof works only for input-transformation reductions. What if we allow Turing reductions? $\endgroup$ Feb 10 at 21:54
$\begingroup$
$\endgroup$
One example of an undecidable language that is not NP-hard, unless P = NP, is $$ L = \{ 1^n : n \text{ is the natural number for a TM which halts on input } \epsilon\}. $$ I have explained this answer through a more general theorem in this answer on mathSE.
answered Mar 14, 2018 at 22:17