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?

  • $\begingroup$ The definition? $\endgroup$ – 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.

  • $\begingroup$ That is very true and a great, concise explanation. Thank you David! $\endgroup$ – 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.

  • $\begingroup$ 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 :) $\endgroup$ – Nyfiken Gul Apr 12 '17 at 10:53
  • 2
    $\begingroup$ 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.) $\endgroup$ – David Richerby Apr 12 '17 at 11:48

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.