間隙定理

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

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

定理由和分別獨立證出。

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

定理敍述
定理的一般形式如下：
:設\Phi為抽象（布盧姆）複雜度衡量。對任意滿足g(x) \ge x（對所有x）的全可計算函數g，都存在嚴格單調的全可計算函數t，使得就\Phi而言，以t為限的複雜性類等於以g \circ t為限的複雜性類。

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

關於時間複雜度的特例，定理可更簡單複述成：
:對任意滿足g(x) \ge 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為限，可以得到同一個複雜度類\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 \ge f的可計算保全算子F，存在嚴格遞增的可計算全函數t，令以t和F t為限的程式編號集相等。

參見
*布盧姆加速定理

參考資料