布鲁姆公理(英语:Blum Axioms),或称布鲁姆复杂度公理(英语:Blum Complexity Axioms),是计算复杂性理论中,定义可计算函数的复杂度时,应满足的条件。这些公理最先由曼纽尔·布鲁姆于1967年提出。[1]
重要的是,只要复杂度衡量满足这些公理,布卢姆加速定理和间隙定理就成立。满足这些公理的复杂度衡量里,最有名的是有关时间(见时间复杂度)和空间(见空间复杂度)的复杂度。
定义
布鲁姆复杂度衡量是一个二元组 ,其中 是偏可计算函数集 的哥德尔编号,而 是一个可计算函数,满足以下的布鲁姆公理。用 表示哥德尔编号 下的第i个偏可计算函数, 表示偏可计算函数 。
- 函数 和 的定义域相同。
- 集合 是递归的。
例子
在定义中, 应当理解成 所编码的计算过程,在输入为 时,所消耗的资源(例如时间、空间,或两者的适当组合)。
- 若 测量时间,则 是复杂度衡量:需要的时间或计算量可计算,因为可以直接模拟。而第二条公理也成立,因为要判断 是否成立,只需运行至多 步,所以总能在有限时间内判断。
- 若 测量空间(内存),则 亦为复杂度衡量,但原因较时间复杂:当限制空间为 时,整个系统的可能状态只有有限多个(例如若图灵机有 个状态,其纸带有 种符号,则纸带共只有 种可能性,最后乘上读写头位置的 种可能性,整个系统只有 种可能性)。从而,只要模拟足够长的时间,必有以下三者之一:
- 计算结束;
- 整个系统重复某个状态,受困于死循环;
- 超出空间限制 。
- 所以,在有限时间内,可以判断 是否成立。
- 作为反例, 并非一个复杂度衡量,因为其不满足第二条公理。
与计算模型的关系
布卢姆的复杂度定义不取决于具体的计算模型,但也可以图灵机的用语复述一次,帮助理解。
布鲁姆复杂度衡量是将二元组(图灵机 ,输入 )射去自然数或 的映射 ,其满足以下公理(对应前述定义):
- 为 当且仅当 不停机。
- 有算法可以判断,当输入 时,是否有 。
例如, 可以是 输入 时运行至停机所需的步数。按定义可知第一条公理成立。而且,用通用图灵机模拟 输入 并运行 步,就是满足第二条公理条件的算法。
复杂度类
对于全可计算函数 ,可计算函数的复杂度类可定义成
-
-
是所有复杂度小于 的可计算函数构成的集合。 是复杂度比 小的布尔函数集合。若我们视这些函数为集合的指示函数,则可视 为集合的复杂度类。
参考文献