2
$\begingroup$

Text

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bernardo Subercaseaux Aug 24 at 3:52
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – orlp Aug 25 at 11:30
  • $\begingroup$ @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. $\endgroup$ – A.M. Aug 25 at 12:30
  • $\begingroup$ The point is, since those constants are undecidable, you can not give the algorithm, and thus you didn't construct a reduction. $\endgroup$ – orlp Aug 25 at 12:58
  • $\begingroup$ @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. $\endgroup$ – A.M. Aug 25 at 13:52

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.