110.1 引言10.2 P 类10.3 NP 类10.4 NP 完全问题10.5 co-NP 类( 略)10.6 NPI 类( 略)10.7 四种类之间的关系( 略)10.x 近似算法初步210.1 引言 在前面的各章中,我们对一些算法的设计和分析进行在前面的各章中,我们对一些算法的设计和分析进行了讨论,这些算法的运行时间可用低次多项式来表示。了讨论,这些算法的运行时间可用低次多项式来表示。在这一章,我们将注意力集中在这样一类问题,这些问在这一章,我们将注意力集中在这样一类问题,这些问题至今没有找到有效算法,而且今后也有可能证明它们题至今没有找到有效算法,而且今后也有可能证明它们不存在有效算法。不存在有效算法。 设设是任意问题,如果对该问题存在一个算法,它的是任意问题,如果对该问题存在一个算法,它的时间复杂性是时间复杂性是O(nO(nkk),其中,其中nn是输入大小、是输入大小、kk是非负整数,是非负整数,我们说问题我们说问题存在多项式时间算法。现实世界的许多问存在多项式时间算法。现实世界的许多问题并不属于这个范畴,因为求解这些问题耗费的时间需题并不属于这个范畴,因为求解这些问题耗费