Are all undecidable problems NP-Hard?

Question

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

Answer 1

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

Answer 2

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.