[拼音]：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的计算有多快，总可以找到另一台机器，它比Mi能更快地计算f。这里用“快”(或“慢”)来表示计算时消耗的资源量的少（或多）。

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

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

严正声明：本文由历史百科网注册或游客用户任彦绮自行上传发布关于» 公理复杂性理论的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：任彦绮；本文链接：https://www.freedefine.cn/wenzhan/56431.html