間隙定理

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

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

定理由鮑里斯·特拉赫堅布羅特（英語：Boris Trakhtenbrot）^[2]和艾倫·鮑羅丁（英語：Allan Borodin）^[3][4]分別獨立證出。

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

定理敍述

定理的一般形式如下：

設${\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}$為限的程式編號集相等。

參見

• 布盧姆加速定理