# Relation between Undecidable problems and NP-Hard

I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.
And then, I realized that it is not certain where undecidable problems should be placed.
Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)
I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.

And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)

• I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable. – sdcvvc Dec 10 '18 at 7:41

I believe that this answer by Yuval Filmus all the questions you have asked.

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

To summarize,

1. Halting problem is NP-hard.
2. If $$P\ne NP$$, not all undecidable problems are NP-hard.
3. If $$P = NP$$, all non-trivial sets are NP-hard.

The original answer had not addressed the last part of your question, namely, are there problems which are neither NP nor NP Hard? I will be lazy again and quote another answer, this time by Peter Shor.

There is a problem which is both NP-hard and in coNP if and only if NP = coNP.

If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.

On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have coNP ⊆ NP. This means NP = coNP.

The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.

So, assuming $$NP \ne coNP$$, there exist problems that are decidable but neither in NP nor NP-hard. Note that we don't know that $$NP = coNP$$ implies $$P = NP$$. So this is a stronger assumption than the one you had suggested ($$P \ne NP$$).

• +1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP. – sdcvvc Dec 10 '18 at 7:40
• "not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct? – Riddle Aaron Dec 10 '18 at 7:55
• @RiddleAaron That sounds right. – Alex Smart Dec 10 '18 at 8:02

Your second diagram seems to be claiming that (assuming $$\mathrm{P}=\mathrm{NP}$$), every $$\mathrm{NP}$$-hard problem that is not $$\mathrm{NP}$$-complete is undecidable. That's certainly not true. For example, by the time hierarchy theorem, we know that $$\mathrm{NEXP}\supsetneq\mathrm{NP}$$. $$\mathrm{NEXP}$$ is a set of decidable problems and it contains $$\mathrm{NP}$$-hard problems that are not in $$\mathrm{NP}$$.