0
$\begingroup$

I'm studying complexity classes and the diagram in NP-Hardness article is confusing to me.

NP-hard has all problems that can be reduced in polynomial time from a problem in NP to them. P is contained in NP. Then it is possible to reduce a problem X in P to a problem Y in NP-hard? This does not add up to me in the scenario P!=NP.

What am I missing here? Is P contained in NP-hard?

$\endgroup$
2
  • $\begingroup$ Check our reference question. $\endgroup$ – Yuval Filmus Apr 24 '20 at 20:36
  • $\begingroup$ That a problem X can be reduced to an NP-hard problem does not mean that X itself is NP-hard. Also, the phrase "all problems that can be reduced in polynomial time from a problem in NP to them" does not really make sense to me, so think through what you mean by this and rephrase it in a way that makes sense; maybe doing so will simultaneously clear up your confusion. $\endgroup$ – HelloGoodbye Feb 11 at 14:56
2
$\begingroup$

NP-hard has all problems that can be reduced in polynomial time from an NP to them.

Not quite: NP-hard consists of all problems to which every NP problem reduces.

Suppose $X\in \mathsf{P}$. If $\mathsf{P}\not=\mathsf{NP}$, then $SAT$ (for example) is not reducible to $X$. So $X$ is not $\mathsf{NP}$-hard: there are some problems in $\mathsf{NP}$ which do not reduce to $X$.

Note that the class of problems to which some problem in $\mathsf{NP}$ reduces is ... the class of all problems whatsoever! This is because (as you observe) once we discard the "edge cases" $\emptyset$ and $\mathbb{N}$, every problem in $\mathsf{P}$ is also in $\mathsf{NP}$, and problems in $\mathsf{P}$ are trivially reducible$^1$ to everything.


$^1$With respect to polynomial-time many-one reducibility. Change the reducibility, and you potentially change the situation. E.g. $\mathsf{P}$ is $\mathsf{NP}$-hard with respect to exponential-time many-one reducibility, since with respect to this reducibility all problems in $\mathsf{NP}$ are trivial.

  • The "many-one" bit is why $\emptyset$ and $\mathbb{N}$ are problematic: no nonempty set is many-one reducible to $\emptyset$, and dually no no set other than $\mathbb{N}$ is many-one reducible to $\mathbb{N}$. This annoyance goes away with more intricate reducibilities, like (variations of) Turing reducibility: literally every problem in $\mathsf{P}$ is reducible to everything with respect to polynomial-time Turing reducibility.

In complexity theory, the default reducibility notion is polynomial-time many-one reducibility. So if we just say "$\mathsf{NP}$-hard" we mean with respect to that reducibility - in which case "there is an $\mathsf{NP}$-hard problem in $\mathsf{P}$" is equivalent to $\mathsf{P=NP}$.

$\endgroup$
6
  • $\begingroup$ It is false that problems in $\mathsf{P}$ are trivially reducible to everything with respect to polynomial-time many-one reducibility. Consider for example the problem $A$ associated with the language $\{0,1\}^*$ and the problem $B$ associated with the language $\emptyset$. $A$ is in $\mathsf{P}$ but is not reducible to $B$. $\endgroup$ – Steven Apr 24 '20 at 17:49
  • $\begingroup$ @Steven Quite right, fixed! $\endgroup$ – Noah Schweber Apr 24 '20 at 19:05
  • $\begingroup$ Sorry for nitpicking :) $\endgroup$ – Steven Apr 24 '20 at 19:20
  • $\begingroup$ @Steven No, it's an important point, thanks for pointing it out! (I personally never work with m-reductions, so to me everything is Turing flavored.) $\endgroup$ – Noah Schweber Apr 24 '20 at 19:41
  • $\begingroup$ Thanks for the answer! After many days reading here and there, i think I finally got it. Can you give references to what are $\emptyset$ and $\mathbb{N}$? $\endgroup$ – Heitor Apr 29 '20 at 14:59
1
$\begingroup$

Let $H$ be the set of $\textsf{NP}$-Hard problems, that is, the set of problems $A$ such that every problem $B \in \textsf{NP}$ can be reduced to $A$ via a Karp reduction.

Then $\textsf{P} \nsubseteq H$. Consider the problem $A$ associated with the language $\emptyset$ and let $B$ be the problem associated with the language $\{0,1\}^*$. Clearly $A \in \textsf{P}$ and $B \in \textsf{P} \subseteq \textsf{NP}$, but $B$ cannot be reduced to $A$ via Karp reduction. This shows that $A \not\in H$, therefore $\textsf{P} \setminus H \neq \emptyset$.

Notice that this is true regardless of whether $\textsf{P} = \textsf{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.