間隙定理

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

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

定理由和分別獨立證出。

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

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

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

關於時間複雜度的特例，定理可更簡單複述成：
對任意滿足（對所有）的全可計算函數，都存在時限，使得，其中DTIME表示確定性圖靈機在限時內能計算的函數的集合。

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

 證明 
鮑羅丁證明的關鍵是，函數在不同自然數的取值可以逐一選取，迫使所有複雜度都不能介乎和之間。具體而言：
定義；
對，定義為最小的自然數，使得，且對所有，有或。

首先，由於滿足布盧姆公理，和兩者皆是可判定的，故上述定義是的-遞歸定義，從而為（偏）可計算函數。

然後，為驗證是全函數，需證明在定義時，滿足條件的存在。對每個，
 若，則總成立；
 否則，希望成立。
所以只要大於之中有限的全部數便可。故有全可計算。

最後，由的定義知，遞增，且對每個，當時，或有，或有，故編號為的可計算函數的複雜度不能介於和之間。

 與加速定理的比較 
原始的間隙定理比上述定理更強：
設是一個複雜度衡量。對任意滿足的全可計算函數，都存在嚴格單調的全可計算函數，令和限制下的程式編號集相等。
這裡的編號指的是附帶的編號 (可計算性理論)。

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

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

 算子間隙定理 
以表示（一元）可計算偏函數的類。映射稱為可（有效）計算算子，若存在全可計算函數，使得對所有成立。此處是編號為的函數。若將全函數映至全函數，則稱保全。間隙定理可複述成：對於由定義的可計算保全算子，可找到令和之間有間隙。證明，同樣的結論對其他可計算保全算子也成立，即：
設為抽象複雜度衡量，則對任意滿足的可計算保全算子，存在嚴格遞增的可計算全函數，令以和為限的程式編號集相等。

 參見 

布盧姆加速定理

 參考資料 

Category:計算複雜性理論
Category:數學定理