間隙定理

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

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

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

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

定理敍述

定理的一般形式如下:

 抽象(布盧姆)複雜度衡量。對任意滿足 (對所有 )的全可計算函數 ,都存在嚴格單調的全可計算函數 ,使得就 而言,以 為限的複雜性類等於以 為限的複雜性類。

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

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

對任意滿足 (對所有 )的全可計算函數 ,都存在時限 ,使得 ,其中DTIME表示確定性圖靈機在限時內能計算的函數的集合。

由於時限 可以很大(且通常不可構),間隙定理無法推出有關複雜度類  的非平凡結果,[5]也不與時間階層定理空間階層定理矛盾。[6]

證明

鮑羅丁[4]證明的關鍵是,函數 在不同自然數的取值 可以逐一選取,迫使所有複雜度 都不能介乎  之間。具體而言:

  • 定義 
  •  ,定義 為最小的自然數 ,使得 ,且對所有 ,有  

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

然後,為驗證 是全函數,需證明在定義 時,滿足條件的 存在。對每個 

  1.  ,則 總成立;
  2. 否則,希望 成立。

所以只要 大於 之中有限的全部數便可。故有 全可計算。

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

與加速定理的比較

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

 是一個複雜度衡量。對任意滿足 的全可計算函數 ,都存在嚴格單調的全可計算函數 ,令  限制下的程式編號集相等。

這裡的編號指的是 附帶的編號 (可計算性理論)

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

誠實性定理

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

算子間隙定理

 表示(一元)可計算偏函數的類。映射 稱為可(有效)計算算子,若存在全可計算函數 ,使得 對所有 成立。此處 編號 的函數。若 將全函數映至全函數,則稱 保全。間隙定理可複述成:對於由 定義的可計算保全算子 ,可找到   之間有間隙。羅伯特·李·康斯特勃英语Robert Lee Constable證明,同樣的結論對其他可計算保全算子也成立,即:[10]

 為抽象複雜度衡量,則對任意滿足 的可計算保全算子 ,存在嚴格遞增的可計算全函數 ,令以  為限的程式編號集相等。

參見

參考資料

  1. ^ Fortnow, Lance; Homer, Steve. A Short History of Computational Complexity [計算複雜性簡史] (PDF). Bulletin of the European Association for Theoretical Computer Science. June 2003, (80): 95–133. (原始内容 (PDF)存档于2005-12-29) (英语). 
  2. ^ Trakhtenbrot, Boris A. The Complexity of Algorithms and Computations (Lecture Notes) [算法與計算的複雜度(講義)]. Novosibirsk University. 1967. 
  3. ^ Allan Borodin. Complexity Classes of Recursive Functions and the Existence of Complexity Gaps [遞歸函數的複雜度類與複雜度間隙的存在性]. Proc. of the 1st Annual ACM Symposium on Theory of Computing. 1969: 67–78 (英语). 
  4. ^ 4.0 4.1 Borodin, Allan. Computational complexity and the existence of complexity gaps [計算複雜度與複雜度間隙的存在性]. Journal of the ACM. January 1972, 19 (1): 158–174. doi:10.1145/321679.321691 (英语). 
  5. ^ Allender, Eric W.; Loui, Michael C.; Regan, Kenneth W., Chapter 7: Complexity Theory, Gonzalez, Teofilo; Diaz-Herrera, Jorge; Tucker, Allen (编), Computing Handbook, Third Edition: Computer Science and Software Engineering [計算手冊,第三版:電腦科學與軟件工程], CRC Press: 7–9, 2014 [2021-08-09], ISBN 9781439898529, (原始内容存档于2021-09-06) (英语), Fortunately, the gap phenomenon cannot happen for time bounds t that anyone would ever be interested in .
  6. ^ Zimand, Marius, Computational Complexity: A Quantitative Perspective [計算複雜度:定量觀點], North-Holland Mathematics Studies 196, Elsevier: 42, 2004 [2021-08-09], ISBN 9780080476667, (原始内容存档于2021-09-04) (英语) .
  7. ^ Borodin, Allan B. Computational Complexity and the Existence of Complexity Gaps [計算複雜度與複雜度間隙的存在性]. Cornell University. 1969 (英语). 
  8. ^ R.Moll; A.R.Meyer. Honest Bounds for Complexity Classes of Recursive Functions [遞歸函數複雜度類的誠實界]. Journal of Symbolic Logic. 1974, 39 (1): 127–138 (英语). 
  9. ^ E. M. McCreight; A. R. Meyer. Classes of computable functions defined by bounds on computation: preliminary report [由計算的限制定義的可計算函數類:初步報告]. Proceedings of the first annual ACM symposium on Theory of computing. 1969: 79–88 (英语). 
  10. ^ Robert L. Constable. The operator gap [算子間隙]. IEEE Conference Record of 10th Annual Symposium on Switching and Automata Theory. 1969: 20–26 (英语).