If P=NP, does this imply that all problems are NP-hard?

Question

A problem is said to be NP-hard if every problem in NP is reducible to that problem in polynomial time. Hence, if P=NP, wouldn't that imply that every problem in NP is reducible to every possible problem, in polynomial time? However the diagram above seems to imply that if P=NP, there exist problems outside of NP-hard.

Is there anything I am missing?

Answer 1

TL;DR: if $\sf P=NP$ then all languages except $\emptyset$ and $\Sigma^*$ are $\sf NP$-hard. The diagram is perhaps misleading if you consider that it has the implication that there are infinitely many problems outside the $\sf NP$-hard region (which you reasonably could, but I didn't assume that from it).

---

We assume throughout that $\sf P=NP$.

Recall that "reducible to" means that we need to map a yes-instance to a yes-instance and a no-instance to a no-instance. This rules out $\emptyset$ and $\Sigma^*$ (the set of all strings), as they lack either a yes- and no-instance.

For all other problems $L$ in $\sf NP$, we can choose a yes-instance $y$ and a no-instance $n$. To reduce $M\in \sf NP$ to $L$, we can just compute in polynomial time whether it is a yes- or no-instance and return $y$ or $n$ accordingly. Thus, the problems in $\sf NP\setminus \{\emptyset, \Sigma^*\}$ are $\sf NP$-hard.

Now let's look at the problems which are not in $\sf NP$ (or, equally, $\sf P$). Consider a $\sf EXP$-complete problem. Such a problem is not in $\sf NP(=P)$ because $\sf P\neq EXP$, so it falls outside the inner circle in the diagram. Additionally, it cannot be $\emptyset$ or $\Sigma^*$ because both problems are in $\sf P$, so the problem has a yes-instance $y$ and a no-instance $n$ and thus we can do the same algorithm above to reduce any $\sf NP$ problem to it in polynomial time. So it meets the definition of $\sf NP$-hard.

The diagram on the right is correct that ${\sf NP\neq NP} \text{-hard}$, but there is a technicality that ${\sf P=NP}\not\subseteq{\sf NP} \text{-hard}$ because of $\emptyset$ and $\Sigma^*$. I think the diagram illustrates this by using $\simeq$ rather than $=$ for the text "NP-complete".

I believe your issue was whether it is meant to say that ${\sf NP} \text{-hard} \neq \mathcal P(\Sigma^*)$, the set of all languages, and indeed that is true but only on a technicality: ${\sf NP} \text{-hard} = \mathcal P(\Sigma^*)\setminus \{\emptyset, \Sigma^*\}$. As for whether the diagram implies this or not, that's a matter of interpretation.

The left diagram doesn't have this right diagram's problem because if $\sf P\neq NP$ then $\emptyset$ and $\Sigma^*$ are in $\sf P$, not $\sf NPC$.