间隙定理

在计算复杂性理论，间隙定理，又称鲍罗丁－特拉赫坚布罗特间隙定理，为与可计算函数复杂度有关的重要定理。

定理断言，复杂性类的层阶之间，有任意大的可计算间隙。意思是，若给定任意一个可计算函数$g$，表示计算资源增加一次的效果，则必能找到某个资源上限$T(n)$，使得即使将资源上限增加一次变成$g(T(n))$，也无法计算更多函数。

定理由鲍里斯·特拉赫坚布罗特和艾伦·鲍罗丁分别独立证出。

虽然特拉赫坚布罗特的推导比鲍罗丁早几年，但时值冷战，该定理直到鲍罗丁发表后才为西方认识。

定理叙述

定理的一般形式如下：

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

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

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

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

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

证明

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

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

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

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

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

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

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

与加速定理的比较

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

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

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

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

诚实性定理

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

算子间隙定理

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

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

参见

• 布卢姆加速定理