# NP-complete and polynomial time reduction

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.

– Raphael
Mar 15, 2013 at 11:05

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.