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

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

定义

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

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

例子

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

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

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

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

与计算模型的关系

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

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

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

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

复杂度类

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

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

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

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

参考文献