算法的“时间复杂度”与“多项式时间求解问题”

算法不是指计算特定问题的实际计算时间，而是指“渐进时间复杂度O（f（n））”，用于表示计算机的能力是否能够胜任问题尺度n的增长。在“多项式时间复杂度”：O（n^k）

中，我们可以研究“多项式时间复杂度”算法在问题大小n增加一个单位：（n+1）^k/n^k=（1+1/n）^k时，以及当问题大小

趋于无穷大，（1+1/n）^k接近1，说明计算时间基本稳定，即计算机功率与问题大小的比较关系呈线性增加。正是在这个意义上，“多项式时间复杂度”的概念并不是指特定程序执行的“时间”，而是指计算机在可计算性意义上的能力，即图灵机的本质，即算法的一般性质，也表达了P区分NP的可计算性。

例如，取 O（2^

n）举例，2^（n+1）/2^n=2表明，当问题大小增加一个单位时，算法执行时间需要加倍，而当输入规模足够大时，计算机的能力不能递增地胜任问题的难度，从而表达了NP的不可计算性。

因此，“多项式时间解算法”可以

从“问题实例多项式时间求解算法”中抽象出来，即P的定义，通常简称为：P是多项式时间算法可以求解的问题类。但是，不能用同样的方式推导：“指数时间解决问题的算法”的概念是从“指数时间解决问题的算法”中抽象出来的，所以流行的观点是“NP是指数时间算法可以解决的问题类，所以NP是可计算的”是错误的。

然而，由于需要分析大量具体问题的定量性质，“多项式时间”

通常引入到特定算法程序的评估中，即比较程序执行所需的计算机时空开销，这是一种可行的特定时间或空间比较关系，但这种实际时间比较关系不同于算法的一般性质，即“多项式时间复杂度”。一般读者很难从这种普遍的误解中理解这种“多项式时间复杂度”的真正含义，即计算机运行的算法的总机器时间或解决问题所需的算法步骤的总时间总和被认为是“多项式时间复杂度”， 而这个“时间”被用来理解P和NP之间的关系，比如关于“多项式时间”的悖论（参见博文：解释一个关于“多项式时间”的悖论），就是这种误解的反映。