跳转到内容

布卢姆公理

维基百科,自由的百科全书

布鲁姆公理(英语:Blum Axioms),或称布鲁姆复杂度公理(英语:Blum Complexity Axioms),是计算复杂性理论中,定义可计算函数的复杂度时,应满足的条件。这些公理最先由曼纽尔·布鲁姆于1967年提出。[1]

重要的是,只要复杂度衡量满足这些公理,布卢姆加速定理间隙定理就成立。满足这些公理的复杂度衡量里,最有名的是有关时间(见时间复杂度)和空间(见空间复杂度)的复杂度。

定义

[编辑]

布鲁姆复杂度衡量是一个二元组,其中偏可计算函数集哥德尔编号,而是一个可计算函数,满足以下的布鲁姆公理。用表示哥德尔编号下的第i偏可计算函数表示偏可计算函数

  1. 函数定义域相同。
  2. 集合递归的

例子

[编辑]

在定义中,应当理解成所编码的计算过程,在输入为时,所消耗的资源(例如时间、空间,或两者的适当组合)。

  • 测量时间,则是复杂度衡量:需要的时间或计算量可计算,因为可以直接模拟。而第二条公理也成立,因为要判断是否成立,只需运行至多步,所以总能在有限时间内判断。
  • 测量空间(记忆体),则亦为复杂度衡量,但原因较时间复杂:当限制空间为时,整个系统的可能状态只有有限多个(例如若图灵机个状态,其纸带有种符号,则纸带共只有种可能性,最后乘上读写头位置的种可能性,整个系统只有种可能性)。从而,只要模拟足够长的时间,必有以下三者之一:
    • 计算结束;
    • 整个系统重复某个状态,受困于死循环;
    • 超出空间限制
所以,在有限时间内,可以判断是否成立。
  • 作为反例,并非一个复杂度衡量,因为其不满足第二条公理。

与计算模型的关系

[编辑]

布卢姆的复杂度定义不取决于具体的计算模型,但也可以图灵机的用语复述一次,帮助理解。

布鲁姆复杂度衡量是将二元组(图灵机,输入)射去自然数或的映射,其满足以下公理(对应前述定义):

  1. 当且仅当停机
  2. 有算法可以判断,当输入时,是否有

例如,可以是输入时运行至停机所需的步数。按定义可知第一条公理成立。而且,用通用图灵机模拟输入并运行步,就是满足第二条公理条件的算法。

复杂度类

[编辑]

对于全可计算函数,可计算函数的复杂度类可定义成

是所有复杂度小于的可计算函数构成的集合。是复杂度比小的布尔函数集合。若我们视这些函数为集合的指示函数,则可视为集合的复杂度类。

参考文献

[编辑]
  1. ^ Blum, Manuel. A Machine-Independent Theory of the Complexity of Recursive Functions (PDF). ACM期刊. 1967, 14 (2): 322–336 [2021-08-09]. doi:10.1145/321386.321395. (原始内容存档 (PDF)于2016-01-15).