# Is P contained in NP-hard?

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?

• Check our reference question. – Yuval Filmus Apr 24 '20 at 20:36
• 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. – HelloGoodbye Feb 11 at 14:56

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

• 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$. – Steven Apr 24 '20 at 17:49
• @Steven Quite right, fixed! – Noah Schweber Apr 24 '20 at 19:05
• Sorry for nitpicking :) – Steven Apr 24 '20 at 19:20
• @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.) – Noah Schweber Apr 24 '20 at 19:41
• 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}$? – Heitor Apr 29 '20 at 14:59

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