If a NP solved in polynomial time, can Satisfiability solved in polynomial time
Based on the below link , I can know that solving of Satisfiability(NP Complete) in polynomial time means any other NP problem can be solved in polynomial time. But is Vice - Versa true?
Also, If there is a polynimial for any other NP-Complete problemt does it mean , all the other NP-Complete can be solved in polynomial time?
What are the differences between NP, NP-Complete and NP-Hard?
The 'complete' in NP-complete means that if a problem is in NP-complete, a solution for that problem gives a solution to any problem in NP with a polynomial amount of conversion processing.
In layman's terms - if you solve a single NP-complete problem in polynomial time you have proven that NP = P.
链接地址: http://www.djcxy.com/p/39992.html