Qfyilyi

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.

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.