Suppose that someone found a polynomial algorithm for a NP-complete decision pro

Question

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?

Explanation / Answer

Recall a few definitions. A language L?{0,1}? is polynomial-time reducible to a language L??{0,1}?, often denoted as L?pL?, if there is a polynomial-time computable function f:{0,1}??{0,1}? such that for every x?{0,1}?, x?L iff f(x)?L?. Now, L? is NP-hard if L?pL? for every L?NP. L? is NP-complete if L? is NP-hard and L??NP.

It is easy to see that if L is NP-hard and L?P, then P=NP. Likewise, if L is NP-complete, then L?P iff P=NP. The intuitive reason is that if f and g are functions that grow at most as nc and nd respectively, then the composition f(g(n)) grows at most ncd, which is also polynomial.

Assume you found a polynomial-time algorithm A for a NP-complete problem X. Now, you could in polynomial time transform another NP-complete problem to X and solve it using A. This is why we often say that it suffices to study whether any NP-complete problem can be decided in polynomial time.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.