間隙定理
維基百科,自由的 encyclopedia
在計算複雜性理論,間隙定理,又稱鮑羅丁-特拉赫堅布羅特間隙定理,為與可計算函數複雜度有關的重要定理。[1]
定理斷言,複雜性類的層階之間,有任意大的可計算間隙。意思是,若給定任意一個可計算函數,表示計算資源增加一次的效果,則必能找到某個資源上限
,使得即使將資源上限增加一次變成
,也無法計算更多函數。
定理由鮑里斯·特拉赫堅布羅特(英語:Boris Trakhtenbrot)[2]和艾倫·鮑羅丁(英語:Allan Borodin)[3][4]分別獨立證出。
雖然特拉赫堅布羅特的推導比鮑羅丁早幾年,但時值冷戰,該定理直到鮑羅丁發表後才為西方認識。
定理敍述
定理的一般形式如下:
- 設
為抽象(布盧姆)複雜度衡量。對任意滿足
(對所有
)的全可計算函數
,都存在嚴格單調的全可計算函數
,使得就
而言,以
為限的複雜性類等於以
為限的複雜性類。
定理可由複雜度衡量需滿足的布盧姆公理證出,而無須牽涉具體的計算模型,故其適用於時間複雜度、空間複雜度,或任何其他合適的複雜度衡量。
關於時間複雜度的特例,定理可更簡單複述成:
由於時限可以很大(且通常不可構),間隙定理無法推出有關複雜度類
或
的非平凡結果,[5]也不與時間階層定理或空間階層定理矛盾。[6]
證明
鮑羅丁[4]證明的關鍵是,函數在不同自然數的取值
可以逐一選取,迫使所有複雜度
都不能介乎
和
之間。具體而言:
- 定義
;
- 對
,定義
為最小的自然數
,使得
,且對所有
,有
或
。
首先,由於滿足布盧姆公理,
和
兩者皆是可判定的,故上述定義是
的
-遞歸定義,從而
為(偏)可計算函數。
然後,為驗證是全函數,需證明在定義
時,滿足條件的
存在。對每個
,
- 若
,則
總成立;
- 否則,希望
成立。
所以只要大於
之中有限的全部數便可。故有
全可計算。
最後,由的定義知,
遞增,且對每個
,當
時,或有
,或有
,故編號為
的可計算函數的複雜度不能介於
和
之間。
與加速定理的比較
原始的間隙定理比上述定理更強:
- 設
是一個複雜度衡量。對任意滿足
的全可計算函數
,都存在嚴格單調的全可計算函數
,令
和
限制下的程式編號集相等。
這裡的編號指的是附帶的編號 (可計算性理論)。
由此可見,沒有程式的複雜度在和
之間。雖然能用複雜度
和複雜度
實現的程式的集合是一樣的,但這只對某些的充分大的
成立。因此,間隙定理與加速定理不同。[7]
誠實性定理
以不同的函數為限,可以得到同一個複雜度類
。此種
稱為該複雜度類的名。時間階層定理和空間階層定理斷言,若限定複雜度類的名具有某種好性質(可構),則不會有太大的間隙。對抽象複雜度而言,也有類似的性質,稱為誠實性(honestness)。以具有此種性質的函數為名的複雜度類之間,並無間隙現象。[8]函數誠實是指其計算複雜度與輸入和輸出相比不太大(用詞源自「函數的值誠實反映其複雜度」)。麥克雷特(E. M. McCraight)和邁耶(A. R. Meyer)證明,以可計算函數為名的複雜度類,總能改名為誠實函數,而不改變其實質。所以,間隙定理的實際源由,是複雜度類改壞名。[9]:86
算子間隙定理
以表示(一元)可計算偏函數的類。映射
稱為可(有效)計算算子,若存在全可計算函數
,使得
對所有
成立。此處
是編號為
的函數。若
將全函數映至全函數,則稱
保全。間隙定理可複述成:對於由
定義的可計算保全算子
,可找到
令
和
之間有間隙。羅伯特·李·康斯特勃(英語:Robert Lee Constable)證明,同樣的結論對其他可計算保全算子也成立,即:[10]
- 設
為抽象複雜度衡量,則對任意滿足
的可計算保全算子
,存在嚴格遞增的可計算全函數
,令以
和
為限的程式編號集相等。
參見
參考資料
- 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) (英語).
- Trakhtenbrot, Boris A. The Complexity of Algorithms and Computations (Lecture Notes) [算法與計算的複雜度(講義)]. Novosibirsk University. 1967.
- 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 (英語).
- 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 (英語).
- 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
. - Zimand, Marius, Computational Complexity: A Quantitative Perspective [計算複雜度:定量觀點], North-Holland Mathematics Studies 196, Elsevier: 42, 2004 [2021-08-09], ISBN 9780080476667, (原始內容存檔於2021-09-04) (英語).
- Borodin, Allan B. Computational Complexity and the Existence of Complexity Gaps [計算複雜度與複雜度間隙的存在性]. Cornell University. 1969 (英語).
- R.Moll; A.R.Meyer. Honest Bounds for Complexity Classes of Recursive Functions [遞歸函數複雜度類的誠實界]. Journal of Symbolic Logic. 1974, 39 (1): 127–138 (英語).
- 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 (英語).
- Robert L. Constable. The operator gap [算子間隙]. IEEE Conference Record of 10th Annual Symposium on Switching and Automata Theory. 1969: 20–26 (英語).