561
个编辑
更改
→Reduction简化
If a problem X is in C and hard for C, then X is said to be complete for C. This means that X is the hardest problem in C. (Since many problems could be equally hard, one might say that X is one of the hardest problems in C.) Thus the class of NP-complete problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem P = NP is not solved, being able to reduce a known NP-complete problem, Π<sub>2</sub>, to another problem, Π<sub>1</sub>, would indicate that there is no known polynomial-time solution for Π<sub>1</sub>. This is because a polynomial-time solution to Π<sub>1</sub> would yield a polynomial-time solution to Π<sub>2</sub>. Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP.]]
If a problem X is in C and hard for C, then X is said to be complete for C. This means that X is the hardest problem in C. (Since many problems could be equally hard, one might say that X is one of the hardest problems in C.) Thus the class of NP-complete problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem P = NP is not solved, being able to reduce a known NP-complete problem, Π<sub>2</sub>, to another problem, Π<sub>1</sub>, would indicate that there is no known polynomial-time solution for Π<sub>1</sub>. This is because a polynomial-time solution to Π<sub>1</sub> would yield a polynomial-time solution to Π<sub>2</sub>. Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP.]]
如果一个问题X在C中并且对于C来说是难问题，那么X对于C来说是完全的。这意味着X是C中最难的问题（因为许多问题可能同样困难，我们可以说X是C中最难的问题之一），因此'''<font color="#ff8000"> 非确定性多项式时间复杂性类完全问题（NP完全问题）</font>'''类包含了NP中最困难的问题，从某种意义上说，它们是可能不在P中的最困难的问题。因为问题P = NP未被解决，如果能够将已知的NP完全问题Π<sub>2</sub>简化为另一个问题Π<sub>1</sub>，则表明Π<sub>1</sub>没有已知的多项式时间解。这是因为Π<sub>1</sub>的多项式时间解会产生Π<sub>2</sub>的多项式时间解。同样，由于所有NP问题都可以归结为集合，找到一个可以在多项式时间内解决的NP完全问题意味着P = NP。]]
如果一个问题X在C中并且对于C来说是难问题，那么X对于C来说是完全的。这意味着X是C中最难的问题（因为许多问题可能同样困难，我们可以说X是C中最难的问题之一），因此'''<font color="#ff8000"> 非确定性多项式时间复杂性类完全问题（NP完全问题）</font>'''类包含了NP中最困难的问题，从某种意义上说，它们是可能不在P中的最困难的问题。因为问题P = NP未被解决，如果能够将已知的NP完全问题Π<sub>2</sub>简化为另一个问题Π<sub>1</sub>，则表明Π<sub>1</sub>没有已知的多项式时间解。这是因为Π<sub>1</sub>的多项式时间解会产生Π<sub>2</sub>的多项式时间解。同样，由于所有NP问题都可以归结为集合，找到一个可以在多项式时间内解决的'''<font color="#ff8000"> NP完全问题</font>'''意味着P = NP。]]
==Important open problems重要的开放性问题==
==Important open problems重要的开放性问题==