# 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.

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.