間隙定理

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

定理斷言，复杂性类的層階之間，有任意大的可計算間隙。意思是，若給定任意一個可計算函數$g$，表示計算資源增加一次的效果，則必能找到某個資源上限$T(n)$，使得即使將資源上限增加一次變成$g(T(n))$，也無法計算更多函數。

定理由Template:Le和Template:Le分別獨立證出。

雖然特拉赫堅布羅特的推導比鮑羅丁早幾年，但時值冷戰，該定理直到鮑羅丁發表後才為西方認識。

定理敍述

定理的一般形式如下：

設$\mathrm{\Phi }$為抽象（布盧姆）複雜度衡量。對任意滿足$g(x)\ge x$（對所有$x$）的全可計算函數$g$，都存在嚴格單調的全可計算函數$t$，使得就$\mathrm{\Phi }$而言，以$t$為限的複雜性類等於以$g\circ t$為限的複雜性類。

定理可由複雜度衡量需滿足的布盧姆公理證出，而無須牽涉具體的計算模型，故其適用於時間複雜度、空間複雜度，或任何其他合適的複雜度衡量。

關於時間複雜度的特例，定理可更簡單複述成：

對任意滿足$g(x)\ge x$（對所有$x$）的全可計算函數$g:\mathbb{N}\to \mathbb{N}$，都存在時限$T(n)$，使得$𝖣𝖳𝖨𝖬𝖤(g(T(n)))=𝖣𝖳𝖨𝖬𝖤(T(n))$，其中DTIME表示確定性圖靈機在限時內能計算的函數的集合。

由於時限$T(n)$可以很大（且通常不可構），間隙定理無法推出有關複雜度類$𝖯$或$𝖭𝖯$的非平凡結果，也不與時間階層定理或空間階層定理矛盾。

證明

鮑羅丁證明的關鍵是，函數$t$在不同自然數的取值$t(n)$可以逐一選取，迫使所有複雜度${\mathrm{\Phi }}_i$都不能介乎$t$和$g\circ t$之間。具體而言：

• 定義$t(0)=1$；
• 對$n\ge 1$，定義$t(n)$為最小的自然數$k$，使得$k>t(n-1)$，且對所有$i\le n$，有${\mathrm{\Phi }}_i(n)<k$或${\mathrm{\Phi }}_i(n)>g(k)$。

首先，由於$\mathrm{\Phi }$滿足布盧姆公理，${\mathrm{\Phi }}_i(n)<k$和${\mathrm{\Phi }}_i(n)>g(k)$兩者皆是可判定的，故上述定義是$t$的$\mu$-遞歸定義，從而$t$為（偏）可計算函數。

然後，為驗證$t$是全函數，需證明在定義$t(n)$時，滿足條件的$k$存在。對每個$i\le n$，

1. 若${\mathrm{\Phi }}_i(n)=\mathrm{\infty }$，則${\mathrm{\Phi }}_i(n)>g(k)$總成立；
2. 否則，希望${\mathrm{\Phi }}_i(n)<k$成立。

所以只要$k$大於${\mathrm{\Phi }}_0(n),{\mathrm{\Phi }}_1(n),\dots ,{\mathrm{\Phi }}_n(n)$之中有限的全部數便可。故有$t$全可計算。

最後，由$t$的定義知，$t$遞增，且對每個$i$，當$n\ge i$時，或有${\mathrm{\Phi }}_i(n)<t(n)$，或有${\mathrm{\Phi }}_i(n)>g(t(n))$，故編號為$i$的可計算函數的複雜度不能介於$t$和$g\circ t$之間。

與加速定理的比較

原始的間隙定理比上述定理更強：

設$\mathrm{\Phi }$是一個複雜度衡量。對任意滿足$g(x)\ge x$的全可計算函數$g$，都存在嚴格單調的全可計算函數$t$，令$t$和$g\circ t$限制下的程式編號集相等。

這裡的編號指的是$\mathrm{\Phi }$附帶的編號 (可計算性理論)。

由此可見，没有程式的複雜度在$t$和$g\circ t$之間。雖然能用複雜度$g\circ t$和複雜度$t$實現的程式的集合是一樣的，但這只對某些的充分大的$t$成立。因此，間隙定理與加速定理不同。

誠實性定理

以不同的函數$t$為限，可以得到同一個複雜度類$\mathrm{C}(t)$。此種$t$稱為該複雜度類的名。時間階層定理和空間階層定理斷言，若限定複雜度類的名具有某種好性質（可構），則不會有太大的間隙。對抽象複雜度而言，也有類似的性質，稱為誠實性（honestness）。以具有此種性質的函數為名的複雜度類之間，並無間隙現象。函數誠實是指其計算複雜度與輸入和輸出相比不太大（用詞源自「函數的值誠實反映其複雜度」）。麥克雷特（E. M. McCraight）和邁耶（A. R. Meyer）證明，以可計算函數為名的複雜度類，總能改名為誠實函數，而不改變其實質。所以，間隙定理的實際源由，是複雜度類改壞名。Template:Rp

算子間隙定理

以${𝒫}^{(1)}$表示（一元）可計算偏函數的類。映射$F:{𝒫}^{(1)}\to {𝒫}^{(1)}$稱為可（有效）計算算子，若存在全可計算函數$S$，使得$F{\phi }_e={\phi }_{S(e)}$對所有$e$成立。此處${\phi }_e$是編號為$e$的函數。若$F$將全函數映至全函數，則稱$F$保全。間隙定理可複述成：對於由$Gf=g\circ f$定義的可計算保全算子$G$，可找到$t$令$t$和$Gt$之間有間隙。Template:Le證明，同樣的結論對其他可計算保全算子也成立，即：

設$\mathrm{\Phi }$為抽象複雜度衡量，則對任意滿足$Ff\ge f$的可計算保全算子$F$，存在嚴格遞增的可計算全函數$t$，令以$t$和$Ft$為限的程式編號集相等。

參見

• 布盧姆加速定理