公理复杂性理论
|
[拼音]：gongli fuzaxing lilun [外文]：axiomatic complexity theory 用公理方法研究部分递归函数的计算复杂性的理论。从空间、时间这样具体的资源中抽象出一般性质，作为抽象资源必须满足的公理。公理复杂性理论就是研究抽象资源耗费的复杂性。假设序列M1，M2，…枚举了全部计算机器，Mi计算了部分递归函数φi(n)，把满足下面两条公理的与 φi有关的递归函数Φi当作计算φi所消耗的抽象资源量。 公理一：Φi(n)有定义，当且仅当φi(n)有定义。 公理二：函数 
是递归函数。 显然，时间、空间都满足上述两条公理，从这些公理出发可得出加速定理、间隙定理和压缩定理。 （1）加速定理：存在取值0，1的递归函数f，对f不存在计算它的最快的机器Mj。换言之，不论Mi对f的计算有多快，总可以找到另一台机器 （2）间隙定理和压缩定理：这是两个相对立的结果，前者说明存在复杂度空穴：[h(n)，g(n，h(n))](n＝1，2，…) 使任何Φi只进入有限次；后者说明Φi的密集性，即任给函数g(n，m)对每个i都有一li，使φ 这是一种早期理论，它使抽象复杂性的研究前进了一步，首次明确地提出资源耗费的问题，强调考虑和比对给定问题的一切可能的算法。另一方面由上述三条定理所反映的病态现象表明过于抽象的理论不能把握实用复杂性的本质。 |
，它比Mi能更快地计算f。这里用“快”(或“慢”)来表示计算时消耗的资源量的少（或多）。
的复杂度Φ
热门点击
最近更新