# Why can there be no reductions from NP-complete problems to P problems under P ≠ NP

Under the assumption that $P \ne NP$, why is it impossible to reduce a problem that is known to be NP-complete to a problem that is known to be of polynomial time complexity? What kind of fundamental theorems would this contradict if it was possible?

• The definition? – Raphael Apr 12 '17 at 20:57

It would contradict the assumption that P$\,\neq\,$NP. You could solve the NP-complete problem in polynomial time by reducing it to a problem in P and solving that.

• That is very true and a great, concise explanation. Thank you David! – Nyfiken Gul Apr 12 '17 at 11:34

This answer was a response to the original version of the question, which has now been edited to ask something different.

Contrary to your premise, it is possible. If $\text{P} \ne \text{NP}$, then any language in $\text{P}$ reduces to an $\text{NP}$-complete problem, but is not $\text{NP}$-complete itself.

In fact we don't need the $\text{P} \ne \text{NP}$ assumption. $\varnothing$ is not $\text{NP}$-complete but reduces easily to $\text{3-SAT}$.

Additional note: it is generally believed that NP-intermediate problems exist (this is equivalent to $\text{P} \ne \text{NP}$). These problems are not in $\text{P}$ and not $\text{NP}$-complete, but they reduce to $\text{NP}$-complete problems.

• Realized now that I miswrote, ment to say from NP-complete to non-NP-complete.. Silly me. Great answer though, made me understand it a lot better! Thank you :) – Nyfiken Gul Apr 12 '17 at 10:53
• Note that even with the original phrasing of the question, it is not necessarily possible to reduce a non-NP-complete problem to an NP-complete one. For example, the halting problem is not NP-complete but cannot be reduced to 3-SAT. (Or, if you prefer something decidable, the same holds, unconditionally, for any NEXP-complete problem.) – David Richerby Apr 12 '17 at 11:48