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

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?

• You probably want to include non-trivial as an hypothesis, as the empty language or $\Sigma^*$ are not NP-hard regardless of whether P=NP or not. – Bernardo Subercaseaux Aug 24 at 3:52

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

• You assumed that finding a yes and no instance of the problem you're reducing to is decidable, but that may not be the case. So I'm not convinced all languages except $\emptyset$ and $\Sigma^*$ are $\sf NP$-hard. – orlp Aug 25 at 11:30
• @orlp Did I? On which line? There just needs to exist a polynomial-time algorithm - it doesn't need to be decidable to find one. $y$ and $n$ are constants hard-coded into the algorithm, not values which the algorithm comes up with. – A.M. Aug 25 at 12:30
• The point is, since those constants are undecidable, you can not give the algorithm, and thus you didn't construct a reduction. – orlp Aug 25 at 12:58
• @orlp Yes, it's a non-constructive argument. I have proven that there is a computable algorithm. It is the decision problem "is this a poly-time reduction from L to M" that is undecidable, not the algorithm itself, which is not only computable but computable in polynomial-time (as required). The decision problem is undecidable for all L,M, regardless of whether L,M are decidable. – A.M. Aug 25 at 13:52