间隙定理

定理的一般形式如下：

设${\displaystyle \Phi }$ 为抽象（布卢姆）复杂度衡量。对任意满足${\displaystyle g(x)\geq x}$ （对所有${\displaystyle x}$ ）的全可计算函数${\displaystyle g}$ ，都存在严格单调的全可计算函数${\displaystyle t}$ ，使得就${\displaystyle \Phi }$ 而言，以${\displaystyle t}$ 为限的复杂性类等于以${\displaystyle g\circ t}$ 为限的复杂性类。

定理可由复杂度衡量需满足的布卢姆公理证出，而无须牵涉具体的计算模型，故其适用于时间复杂度、空间复杂度，或任何其他合适的复杂度衡量。

关于时间复杂度的特例，定理可更简单复述成：

对任意满足${\displaystyle g(x)\geq x}$ （对所有${\displaystyle x}$ ）的全可计算函数${\displaystyle g:\mathbb {N} \to \mathbb {N} }$ ，都存在时限${\displaystyle T(n)}$ ，使得${\displaystyle {\mathsf {DTIME}}(g(T(n)))={\mathsf {DTIME}}(T(n))}$ ，其中DTIME表示确定性图灵机在限时内能计算的函数的集合。

由于时限${\displaystyle T(n)}$ 可以很大（且通常不可构），间隙定理无法推出有关复杂度类${\displaystyle {\mathsf {P}}}$ 或${\displaystyle {\mathsf {NP}}}$ 的非平凡结果，^[5]也不与时间阶层定理或空间阶层定理矛盾。^[6]

鲍罗丁^[4]证明的关键是，函数${\displaystyle t}$ 在不同自然数的取值${\displaystyle t(n)}$ 可以逐一选取，迫使所有复杂度${\displaystyle \Phi _{i}}$ 都不能介乎${\displaystyle t}$ 和${\displaystyle g\circ t}$ 之间。具体而言：

• 定义${\displaystyle t(0)=1}$ ；
• 对${\displaystyle n\geq 1}$ ，定义${\displaystyle t(n)}$ 为最小的自然数${\displaystyle k}$ ，使得${\displaystyle k>t(n-1)}$ ，且对所有${\displaystyle i\leq n}$ ，有${\displaystyle \Phi _{i}(n)<k}$ 或${\displaystyle \Phi _{i}(n)>g(k)}$ 。

首先，由于${\displaystyle \Phi }$ 满足布卢姆公理，${\displaystyle \Phi _{i}(n)<k}$ 和${\displaystyle \Phi _{i}(n)>g(k)}$ 两者皆是可判定的，故上述定义是${\displaystyle t}$ 的${\displaystyle \mu }$ -递归定义，从而${\displaystyle t}$ 为（偏）可计算函数。

然后，为验证${\displaystyle t}$ 是全函数，需证明在定义${\displaystyle t(n)}$ 时，满足条件的${\displaystyle k}$ 存在。对每个${\displaystyle i\leq n}$ ，

1. 若${\displaystyle \Phi _{i}(n)=\infty }$ ，则${\displaystyle \Phi _{i}(n)>g(k)}$ 总成立；
2. 否则，希望${\displaystyle \Phi _{i}(n)<k}$ 成立。

所以只要${\displaystyle k}$ 大于${\displaystyle \Phi _{0}(n),\ \Phi _{1}(n),\ \ldots ,\ \Phi _{n}(n)}$ 之中有限的全部数便可。故有${\displaystyle t}$ 全可计算。

最后，由${\displaystyle t}$ 的定义知，${\displaystyle t}$ 递增，且对每个${\displaystyle i}$ ，当${\displaystyle n\geq i}$ 时，或有${\displaystyle \Phi _{i}(n)<t(n)}$ ，或有${\displaystyle \Phi _{i}(n)>g(t(n))}$ ，故编号为${\displaystyle i}$ 的可计算函数的复杂度不能介于${\displaystyle t}$ 和${\displaystyle g\circ t}$ 之间。

原始的间隙定理比上述定理更强：

设${\displaystyle \Phi }$ 是一个复杂度衡量。对任意满足${\displaystyle g(x)\geq x}$ 的全可计算函数${\displaystyle g}$ ，都存在严格单调的全可计算函数${\displaystyle t}$ ，令${\displaystyle t}$ 和${\displaystyle g\circ t}$ 限制下的程式编号集相等。

这里的编号指的是${\displaystyle \Phi }$ 附带的编号 (可计算性理论)。

由此可见，没有程式的复杂度在${\displaystyle t}$ 和${\displaystyle g\circ t}$ 之间。虽然能用复杂度${\displaystyle g\circ t}$ 和复杂度${\displaystyle t}$ 实现的程式的集合是一样的，但这只对某些的充分大的${\displaystyle t}$ 成立。因此，间隙定理与加速定理不同。^[7]

以不同的函数${\displaystyle t}$ 为限，可以得到同一个复杂度类${\displaystyle \mathrm {C} (t)}$ 。此种${\displaystyle t}$ 称为该复杂度类的名。时间阶层定理和空间阶层定理断言，若限定复杂度类的名具有某种好性质（可构），则不会有太大的间隙。对抽象复杂度而言，也有类似的性质，称为诚实性（honestness）。以具有此种性质的函数为名的复杂度类之间，并无间隙现象。^[8]函数诚实是指其计算复杂度与输入和输出相比不太大（用词源自“函数的值诚实反映其复杂度”）。麦克雷特（E. M. McCraight）和迈耶（A. R. Meyer）证明，以可计算函数为名的复杂度类，总能改名为诚实函数，而不改变其实质。所以，间隙定理的实际源由，是复杂度类改坏名。^[9]:86

以${\displaystyle {\mathcal {P}}^{(1)}}$ 表示（一元）可计算偏函数的类。映射${\displaystyle F:{\mathcal {P}}^{(1)}\to {\mathcal {P}}^{(1)}}$ 称为可（有效）计算算子，若存在全可计算函数${\displaystyle S}$ ，使得${\displaystyle F\varphi _{e}=\varphi _{S(e)}}$ 对所有${\displaystyle e}$ 成立。此处${\displaystyle \varphi _{e}}$ 是编号为${\displaystyle e}$ 的函数。若${\displaystyle F}$ 将全函数映至全函数，则称${\displaystyle F}$ 保全。间隙定理可复述成：对于由${\displaystyle Gf=g\circ f}$ 定义的可计算保全算子${\displaystyle G}$ ，可找到${\displaystyle t}$ 令${\displaystyle t}$ 和${\displaystyle Gt}$ 之间有间隙。罗伯特·李·康斯特勃（英语：Robert Lee Constable）证明，同样的结论对其他可计算保全算子也成立，即：^[10]

设${\displaystyle \Phi }$ 为抽象复杂度衡量，则对任意满足${\displaystyle Ff\geq f}$ 的可计算保全算子${\displaystyle F}$ ，存在严格递增的可计算全函数${\displaystyle t}$ ，令以${\displaystyle t}$ 和${\displaystyle Ft}$ 为限的程式编号集相等。

• 布卢姆加速定理