A decision problem is NP-complete if it is in NP and all other problems in NP can be reduced to it by a reduction that runs in polynomial time. Why it is important to require that the reduction runs in polynomial time, as opposed to accepting any computable reduction.


If there is no resource bound for the reduction and you want to reduce problem A to problem B then there is a trivial "reduction" algorithm for any computable A - simply compute the answer for problem A.

  • $\begingroup$ See en.wikipedia.org/wiki/Reduction_(complexity): However, in order to be useful, reductions must be easy. For example, it's quite possible to reduce a difficult-to-solve NP-complete problem like the boolean satisfiability problem to a trivial problem, like determining if a number equals zero, by having the reduction machine solve the problem in exponential time and output zero only if there is a solution. However, this does not achieve much, because even though we can solve the new problem, performing the reduction is just as hard as solving the old problem. $\endgroup$ – Massimo Cafaro Mar 12 '13 at 13:48
  • $\begingroup$ Continued from previous comment: Likewise, a reduction computing a noncomputable function can reduce an undecidable problem to a decidable one. As Michael Sipser points out in Introduction to the Theory of Computation: "The reduction must be easy, relative to the complexity of typical problems in the class [...] If the reduction itself were difficult to compute, an easy solution to the complete problem wouldn't necessarily yield an easy solution to the problems reducing to it." $\endgroup$ – Massimo Cafaro Mar 12 '13 at 13:51

In order to fully understand this, think about the purpose of reductions. Ideally, given a language (or problem) $L$, you would design an algorithm deciding $L$ and prove that no other algorithm can do better than your algorithm. The latter part implies proving a lower bound for the problem $L$. Designing an algorithm is the easiest part, but proving a lower bounds for most of the problems we care about may be extremely difficult. Indeed, for many problems we have no idea of how to prove a lower bound. So what to do about? Instead of proving a lower bound, we relate the difficulty of problems to each other using reductions, and prove that a problem is a hardest problem in a complexity class through completeness. Reductions are a powerful, and useful surrogate for our inability of proving lower bounds. For $NP-Complete$ problems, no one succeeded until now in proving a polynomial lower bound or proving a super-polynomial lower bound.

We can use reductions in two different ways, either in positive or negatively. For a positive usage example, consider a new problem $L_1$, reduce it to $L$ that you know already to be in $P$. Now you can conclude that $L_1 \in P$ as well. This formalizes in some way the idea that $L_1$ is as easy as $L$. For a negative usage example, reduce $L_1$ to $L$ that you believe this time not to be in $P$. You may now conclude that $L_1$ does not belong to $P$ if $L$ does not belong to $P$. This formalizes the idea that $L_1$ is as hard as $L$. Completeness formalizes the idea that a language $L$ is one of the hardest problems in a complexity class $C$. In order for the previous ideas to work we require that reductions must be "efficient", i.e. polytime.

For the positive usage example given above, if the reduction algorithm were super-polynomial, the entire reasoning would be useless: even knowing a polynomial time algorithm for $L$ (a function $g$) would not help to solve $L_1$ in polynomial time, since you need to "transform" the polynomial solution for $L$ in the corresponding solution for $L_1$ via the reduction (a function $f$). If the reduction is super-polynomial, the the compositions $f(g(x))$ and $g(f(x))$ of this two functions are not polynomial.

In particular, for $NP-Complete$ problems, if we find a polynomial time algorithm for one, we automatically have found one for $all$ $NP$ problems. But this only works if we restrict reductions to be polytime computable.


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.