So, I need answer to question in title: Are all undecidable problems NP-hard? What I mean is if I have some undecidable problem (for example, Post correspondance problem) can I say it's NP-hard and how to prove it?

  • $\begingroup$ I think this should be closed, but I'm not sure what should it be closed as... You should probably post the link to the answer as a CW answer. $\endgroup$ – tomasz Jan 18 '14 at 18:53
  • $\begingroup$ @tomasz: I copied answer from link (it wouldn't let me write just link,it's too short for answer :P). Is this ok? $\endgroup$ – Meow Jan 18 '14 at 19:02
  • $\begingroup$ Yeah, I suppose it is. I slightly improved the presentation. You should also accept it as soon as you can. $\endgroup$ – tomasz Jan 18 '14 at 23:04
  • $\begingroup$ Ok, thank you for help =) $\endgroup$ – Meow Jan 19 '14 at 10:39

Answer by Yuval Filmus, original post at cs.se:

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


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 find the example quite natural; it doesn't require diagonalization to construct. It is also nice because the example is RE, and moreover, we can replace "for a TM which halts on input $\epsilon$" with any undecidable property. In fact we have the following result:

Theorem. Let $A \subseteq \{0,1\}^*$ consist of only unary strings, i.e. $A \subseteq 1^*$. Then $A$ cannot be NP-hard, unless P = NP.

This theorem can be used to find interesting and natural counterexamples to your question and related questions.

To prove it, we suppose that $A$ is NP-hard; then there is a poly-time reduction $f$ from SAT to $A$. We use $f$ to design a poly-time algorithm for SAT, proving that P = NP. On input $\phi$, pick a variable $x_1$, and try plugging in $x_1 = $True and $x_1 = $False, yielding $\phi_1$ and $\phi_2$, then apply $f$ to each reduced formula. If $f(\phi_1)$ is not unary, then $\phi_1$ must not be satisfiable, so we repeat with $\phi_2$. Similarly if $f(\phi_2)$ is not unary. The hard case is where both $f(\phi_1)$ and $f(\phi_2)$ are unary. Then we keep track of both $\phi_1$ and $\phi_2$, and now plug in $x_2 = $True and $x_2 = $False. However, if we ever get the same string after applying $f$, we remove duplicates. Since there are only polynomially many unary strings we could get applying $f$ (since it is a poly-time reduction), we only ever have to keep track of polynomially many reduced formulas at once (we are checking if any of these formulas is satisfiable). Ultimately, we end up trying an assignment to all variables, at which point we can just check for each of the polynomially many remaining assignments whether they satisfy the formula.

| cite | improve this answer | |

The wikipedia article on NP-hardness addresses part of your question in the second paragraph of the examples section.

It lists the halting problem as an example of an undecidable problem that is NP-hard because of how a turing machine may be transformed into truth value assignments.

If $P=NP$ then all undeciable problems are NP-hard...so are all decidable problems. The oracle can just be ignored. So to disprove that undecidable problems are NP-hard you'd have to somehow prove $P \ne NP$.

To prove your proposition in the affirmative, that for all undecidable problems, an oracle for that problem can be used to solve an NP-complete problem in polynomial time might not be much easier, but others here probably know more than me about that.

| cite | improve this answer | |
  • 1
    $\begingroup$ You did not really answer the question... $\endgroup$ – tomasz Jan 18 '14 at 18:50
  • $\begingroup$ That is correct, I answered the part of it that I could, which I think would be more appropriate for a comment but it was a bit too long. $\endgroup$ – DanielV Jan 18 '14 at 19:09
  • $\begingroup$ I think you should just post a few comments in such a case, but this is just my opinion. Note that I am not the person who downvoted your answer, if that's what you were thinking. (I did downvote the other answer which is just plain wrong, though...) $\endgroup$ – tomasz Jan 18 '14 at 23:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.