什么是公理复杂性理论?

[拼音]：gongli fuzaxing lilun

[外文]：axiomatic complexity theory

用公理方法研究部分递归函数的计算复杂性的理论。从空间、时间这样具体的资源中抽象出一般性质，作为抽象资源必须满足的公理。公理复杂性理论就是研究抽象资源耗费的复杂性。假设序列M₁，M₂，…枚举了全部计算机器，M_i计算了部分递归函数φ_i(n)，把满足下面两条公理的与 φ_i有关的递归函数Φ_i当作计算φ_i所消耗的抽象资源量。

公理一：Φ_i(n)有定义，当且仅当φ_i(n)有定义。

公理二：函数

是递归函数。

显然，时间、空间都满足上述两条公理，从这些公理出发可得出加速定理、间隙定理和压缩定理。

（1）加速定理：存在取值0，1的递归函数f，对f不存在计算它的最快的机器M_j。换言之，不论M_i对f的计算有多快，总可以找到另一台机器


，它比M_i能更快地计算f。这里用“快”(或“慢”)来表示计算时消耗的资源量的少（或多）。

（2）间隙定理和压缩定理：这是两个相对立的结果，前者说明存在复杂度空穴：[h(n)，g(n，h(n))](n＝1，2，…) 使任何Φ_i只进入有限次；后者说明Φ_i的密集性，即任给函数g(n，m)对每个i都有一l_i，使φ


的复杂度Φ


(n)几乎处处介于Φ_i(n)与g(n，Φ_i(n))之间。

这是一种早期理论，它使抽象复杂性的研究前进了一步，首次明确地提出资源耗费的问题，强调考虑和比对给定问题的一切可能的算法。另一方面由上述三条定理所反映的病态现象表明过于抽象的理论不能把握实用复杂性的本质。