算法| NP完全|问题1

假设P！=NP，以下哪项是正确的？ （A） NP完全=NP （B） NP完全 P= （C） NP-hard=NP （D） P=NP完全 （A） A. （B） B （C） C （D） D 答复: （B） 说明： 答案是B（不是） 全类 问题可以在多项式时间内解决）。因为，如果一个NP完全问题可以在多项式时间内求解，那么所有NP问题都可以在多项式时间内求解。如果是这样的话，那么NP和P集变得相同，这与给定的条件相矛盾。 这个问题的小测验