間隙定理

在計算複雜性理論，間隙定理，又稱鮑羅丁－特拉赫堅布羅特間隙定理，為與可計算函數複雜度有關的重要定理。

定理斷言，複雜性類的層階之間，有任意大的可計算間隙。意思是，若給定任意一個可計算函數$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$為限的程式編號集相等。

參見

• 布盧姆加速定理