布卢姆公理

布鲁姆复杂度衡量是一个二元组${\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)}$ 为集合的复杂度类。