6
$\begingroup$

enter image description here

enter image description here

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)

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – sdcvvc Dec 10 '18 at 7:41
8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ +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. $\endgroup$ – sdcvvc Dec 10 '18 at 7:40
  • $\begingroup$ "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? $\endgroup$ – Riddle Aaron Dec 10 '18 at 7:55
  • $\begingroup$ @RiddleAaron That sounds right. $\endgroup$ – Alex Smart Dec 10 '18 at 8:02
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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