Cfrtjryk

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

NP-Hard means "at least as hard as the hardest problems in NP"! Hence, all the problems such as halting problem which is not decidable, is in NP-Hard but not in NP. See this page.

There are decision problems that are NP-hard but not NP-complete, for example the halting problem.

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}supsetneqmathrm{NP}$. $mathrm{NEXP}$ is a set of decidable problems and it contains $mathrm{NP}$-hard problems that are not in $mathrm{NP}$.