# Reduction from P to NP

Conceptually, I know that reducing a problem $Y$ that's NP-complete to a problem $X$ implies that $X$ is at least as hard as $Y$, implying $X$ is also NP-complete. So if any NPC problem, say $Z$, can be solved in polynomial time, then that implies $P = NP$, since any other NP-complete problem can be reduced to $Z$ in polynomial time, and then solved in polynomial time. But what does it mean to reduce a problem in $P$ to a problem in $NP$? I feel like this is self-evident (problems in P are no harder than problems in $NP$), but is there any example that can make this clearer?

• When taking boolean formulas, we can say that HornSAT already is a subcase of SAT and thus a member of NP. And in fact every NPC problem under some restrictions becomes P problem. – rus9384 Nov 13 '17 at 12:19
• " implying X is also NP-complete" -- only if X is in NP. – Raphael Nov 13 '17 at 12:28
• " I feel like this is self-evident" -- pretty much, yes. Follow the definitions. – Raphael Nov 13 '17 at 12:28

If $A$ belongs to $P$, then we can reduce $A$ to any nontrivial language, i.e. any $B\neq \emptyset,\Sigma^*$.
Reducing $A$ to $B$ can be done as follows. Fix $b_1\in B, b_0 \in \overline B$ arbitrarily. The reduction algorithm then takes an input $x$ and tests whether $x\in A$: if that holds, return $b_1$, otherwise return $b_0$.
Note that all of this can be run in polynomial time since $A$ belongs to $P$. This allows to solve the $A$ instance in the reduction algorithm itself, trivializing the reduction.
This proves that problems in $P$ are indeed the easiest possible ones, according to the "polynomial-time reduction" preorder.