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