计算复杂性

也称算法复杂性，是可计算性理论的新发展，研究一可计算函数f的内在复杂性如何，能否找到计算f的“最好”程序这一类问题。

衡量算法(计算)的复杂程度，最常用的尺度是计算时间(计算步数)。在讨论计算复杂性时常使用多带图灵机作计算模型。函数

称为e(第e号图灵机)的时间消耗函数。

利用T(e，x)可以对一元递归全函数进行分类。

设b(x)是递归全函数，函数类

=｛｜是全函数且T(e，x)≤b(x)a．e｝

称作b的复杂性类。其中“T(e，x)≤b(x)a．e”意义为至多有有穷多个x使“T(e，x)≤b(x)”不成立。

最令人感兴趣的是b为多项式的情形。以表示全体一元多项式的类，则

称为多项式有界时间可计算的一元函数类(参见P=NP问题)。

上述分类方法可以得到无穷多个类。下面的定理1表明，存在任意复杂的可计算函数，任何一个都不能包括全体递归函数。

定理1．令b是一元递归全函数，存在递归全函数f(x)使得如果φ=f

则T(e，x)＞b(x)a．e。

这种分类方法并不是分层方法。著名的勃拉姆加速定理说：

定理2(加速定理)设r是任意的递归全函数(例如r(x)=2x)，存在一个递归全函数f，使得任给φ=f，存在φ=f满足

r(T(k，x))＜T(e，x)a．e(例如2T(k，x)＜T(e，x)a．e)

也就是说f没有最快的算法，因而对f并没有一个特定的类使f∈但不属更快的复杂类。

还有一条重要定理叫作空隙定理。

定理3(空隙定理)令r是递归全函数，r(x)≥x。存在递归全函数b使

(a)、对任何e，x，如果e＜x、T(e，x)有定义且T(e，x)＞b(x)，则T(e，x)＞r(b(x))。

也就是说与之间再无其他的复杂性类。

对于多元函数φ(x，…，x)也可以定义

(其中=(x，…，x))。

对递归全函数b(x)，可以定义复杂性类

是全函数，T(e，)≤b(max())a．e｝。

利用可以对初等函数作分类，定义b为：

定理4．设是初等函数类，则

(参见初等函数)。

另一个常用的复杂性尺度是空间消耗函数：

利用S(e，x)也可以对递归函数分类，这方面最令人感兴趣的是

PSPACE=｛φ｜存在多项式函数p(x)使s(e，x)≤p(x)｝

称为确定性图灵机多项式空间有界可计算函数类。现已知道：PSPACE=NP

一般说来，如果函数列Φ，Φ，…Φ，…满足

(a)．对每个e，Dom()=Dom()

(b)．谓词“Φ(x)=y”是递归谓词，则Φ都可作为复杂性尺度。