门|门CS 2012 |问题4

Assuming P != NP, which of the following is true ?
(A) NP-complete = NP
(B) NP-complete  P = 
(C) NP-hard = NP
(D) P = NP-complete

（A） A. （B） B （C） C （D） D 答复: （B） 说明：

答案是B（不是） 全类 问题可以在多项式时间内解决）。因为，如果一个NP完全问题可以在多项式时间内求解，那么所有NP问题都可以在多项式时间内求解。如果是这样的话，那么NP和P集变得相同，这与给定的条件相矛盾。

相关文章： NP完备性|集1（简介） P/NP问题 （维基百科） 这个问题的小测验