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.
2
$\begingroup$
$\endgroup$
migrated from cstheory.stackexchange.com Mar 12 '13 at 16:49
This question came from our site for theoretical computer scientists and researchers in related fields.
-
$\begingroup$ I suggest you read the answers to this question. $\endgroup$ – Raphael♦ Mar 15 '13 at 11:05
3
$\begingroup$
$\endgroup$
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
1
$\begingroup$
$\endgroup$
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.
