布卢姆公理

布鲁姆公理(英语: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).