Is P contained in NP-hard?

Question

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?

Answer 1

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

Answer 2

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