布卢姆公理

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

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

定义

布鲁姆复杂度衡量是一个二元组$(\varphi ,\Phi )$，其中$\varphi$是偏可计算函数集$\mathbf {P} ^{(1)}$的哥德尔编号，而$\Phi :\mathbb {N} \to \mathbf {P} ^{(1)}$是一个可计算函数，满足以下的布鲁姆公理。用$\varphi _{i}$表示哥德尔编号$\varphi$下的第i个偏可计算函数，$\Phi _{i}$表示偏可计算函数$\Phi (i)$。

1. 函数$\varphi _{i}$和$\Phi _{i}$的定义域相同。
2. 集合$\{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\}$是递归的。

例子

在定义中，$\Phi _{i}(x)$应当理解成$i$所编码的计算过程，在输入为$x$时，所消耗的资源（例如时间、空间，或两者的适当组合）。

• 若$\Phi$测量时间，则$(\varphi ,\Phi )$是复杂度衡量：需要的时间或计算量可计算，因为可以直接模拟。而第二条公理也成立，因为要判断$\Phi _{i}(x)=t$是否成立，只需运行至多$t$步，所以总能在有限时间内判断。
• 若$\Phi$测量空间（记忆体），则$(\varphi ,\Phi )$亦为复杂度衡量，但原因较时间复杂：当限制空间为$t$时，整个系统的可能状态只有有限多个（例如若图灵机有$q$个状态，其纸带有$s$种符号，则纸带共只有$s^{t}$种可能性，最后乘上读写头位置的$t$种可能性，整个系统只有$qs^{t}t$种可能性）。从而，只要模拟足够长的时间，必有以下三者之一：
  • 计算结束；
  • 整个系统重复某个状态，受困于无穷回圈；
  • 超出空间限制$t$。

所以，在有限时间内，可以判断$\Phi _{i}(x)=t$是否成立。

• 作为反例，$(\varphi ,\varphi )$并非一个复杂度衡量，因为其不满足第二条公理。

与计算模型的关系

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

布鲁姆复杂度衡量是将二元组（图灵机$M$，输入$x$）射去自然数或$\infty$的映射$\Phi$，其满足以下公理（对应前述定义）：

1. $\Phi (M,x)$为$\infty$当且仅当$M(x)$不停机。
2. 有算法可以判断，当输入$(M,x,t)$时，是否有$\Phi (M,x)=t$。

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

复杂度类

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

$C(f):=\{\varphi _{i}\in \mathbf {P} ^{(1)}|\forall x.\ \Phi _{i}(x)\leq f(x)\},$

$C^{0}(f):=\{h\in C(f)|\mathrm {codom} (h)\subseteq \{0,1\}\}.$

$C(f)$是所有复杂度小于$f$的可计算函数构成的集合。$C^{0}(f)$是复杂度比$f$小的布尔函数集合。若我们视这些函数为集合的指示函数，则可视$C^{0}(f)$为集合的复杂度类。