在算法理论中，算法的“时间复杂度”并不是指计算具体问题的实际计算时间，而是指“渐进时间复杂度O(f(n))”，用来表达计算机的能力对问题的规模n的增长是否胜任，这里的“计算机的能力”或“问题的规模”不是“常量”，而是“变量”，指能力和规模的增长趋势，O(f(n))反应的是比值函数关系。

于“多项式时间复杂度”：O(n^k)，可以考察当问题规模n增加一个单位时，“多项式时间复杂度”的算法的计算时间的变化趋势：（n＋1)^k/n^k＝(1+1/n)^k，当问题规模趋近无穷时，（1+1/n)^k趋近1，表明计算时间基本保持稳定，即计算机的能力与问题的规模是线性增长的比较关系。正是在此意义上，“多项式时间复杂度”这个概念并非指具体程序执行的“时间”，而是指在可计算性意义上计算机的能力，即图灵机的本质，也就是算法的一般性质，也由此表达了P的可计算性意义，用以区分NP。

与之相对应的另一个算法复杂度“指数时间”：O(c^n)，比如，以O(2^n)为例，2^(n＋1)/2^n＝2，表明当问题规模增加一个单位时，算法执行时间需翻倍，当输入规模充分大时，计算机的能力对问题的困难程度不是增长性胜任的，由此表达了NP的不可计算性意义。

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

然而，由于大量的具体问题的定量性质分析需要，“多项式时间”通常被引入到对具体算法程序的评价，即以程序执行所要求的计算机时空开销进行比较，这是一种可行的具体的时间或空间的比较关系，但这种实际时间比较关系与“多项式时间复杂度”所表达的算法的一般性质是有区别的。一般读者很难从这种广泛存在的误解中理解到这个“多项式时间复杂度”的真正意义，由此产生的误解就是将计算机运行的算法的全部机器时间或要解决的问题所要求的算法步骤的总和时间被认为就是“多项式时间复杂度”，并以这种“时间”来理解P和NP之间的关系，比如关于“多项式时间”的悖论（见博文：解读关于“多项式时间”的一个悖论 http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&id=917832），就是这种误解的反映。