Problem Detail: Suppose that someone found a polynomial algorithm for a NP-complete decision problem. Would this mean that we can modify the algorithm a bit and use it for solving the problems that are in NP, but not in NP-complete? Or would this just shows the availability of a polynomial algorithm for each NP problem indirectly? edit: I know that when NP-complete problems have polynomial algorithms, all NP problems must have polynomial algorithms. The question I am asking is that whether we can use the discovered algorithm for NP-complete to all NP problems just by modifying the algorithm. Or would we just know that NP problems must have a polynomial algorithm indirectly?
Asked By : Zat Mack
Answered By : Juho
Recall a few definitions. A language $L subseteq {0,1}^*$ is polynomial-time reducible to a language $L’ subseteq {0,1}^*$, often denoted as $L leq_p L’$, if there is a polynomial-time computable function $f : {0,1}^* to {0,1}^*$ such that for every $x in {0,1}^*$, $x in L$ iff $f(x) in L’$. Now, $L’$ is $text{NP}$-hard if $L leq_p L’$ for every $L in text{NP}$. $L’$ is $text{NP}$-complete if $L’$ is $text{NP}$-hard and $L’ in text{NP}$. It is easy to see that if $L$ is $text{NP}$-hard and $L in text{P}$, then $text{P} = text{NP}$. Likewise, if $L$ is $text{NP}$-complete, then $L in text{P}$ iff $text{P} = text{NP}$. The intuitive reason is that if $f$ and $g$ are functions that grow at most as $n^c$ and $n^d$ respectively, then the composition $f(g(n))$ grows at most $n^{cd}$, which is also polynomial. Assume you found a polynomial-time algorithm $A$ for a $text{NP}$-complete problem $X$. Now, you could in polynomial time transform another $text{NP}$-complete problem to $X$ and solve it using $A$. This is why we often say that it suffices to study whether any $text{NP}$-complete problem can be decided in polynomial time.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2653
