查看“︁間隙定理”︁的源代码

在[[計算複雜性理論]]，'''間隙定理'''，又稱'''鮑羅丁－特拉赫堅布羅特間隙定理'''，為與[[可计算函数]]複雜度有關的重要定理。<ref>{{Cite journal
 |first        = Lance
 |last         = Fortnow
 |first2       = Steve
 |last2        = Homer
 |title        = A Short History of Computational Complexity
 |trans-title  = 計算複雜性簡史
 |url          = http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column80.pdf
 |archive-url  = https://web.archive.org/web/20051229063702/http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column80.pdf
 |url-status     = dead
 |archive-date = 2005-12-29
 |journal      = Bulletin of the European Association for Theoretical Computer Science
 |pages        = 95–133
 |issue        = 80
 |date         = June 2003
 |language     = en
}}</ref>

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

定理由{{le|鮑里斯·特拉赫堅布羅特|Boris Trakhtenbrot}}<!--Трахтенброт依[[WP:外語譯音表/俄語]]暫譯--><ref>{{cite book|last=Trakhtenbrot|first=Boris A.|title=The Complexity of Algorithms and Computations (Lecture Notes) | trans-title = 算法與計算的複雜度（講義）|date=1967|publisher=Novosibirsk University}}</ref>和{{le|艾倫·鮑羅丁|Allan Borodin}}<!--依[[:wikt:Allan]]和[[:wikt:Borodin]]--><ref>{{cite journal|author=Allan Borodin|title=Complexity Classes of Recursive Functions and the Existence of Complexity Gaps|trans-title = 遞歸函數的複雜度類與複雜度間隙的存在性|journal=Proc. of the 1st Annual ACM Symposium on Theory of Computing|pages=67–78|date=1969 |language = en}}</ref><ref name = "Bor72">{{cite journal|author=Borodin, Allan|title=Computational complexity and the existence of complexity gaps|trans-title =計算複雜度與複雜度間隙的存在性|journal=[[ACM期刊|Journal of the ACM]]|volume=19|issue=1|pages=158–174|date=January 1972 |doi=10.1145/321679.321691 |language = en}}</ref>[[重复独立发现发明列表|分別獨立]]證出。

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

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

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

關於時間複雜度的特例，定理可更簡單複述成：
:對任意滿足<math>g(x) \ge x</math>（對所有<math>x</math>）的全可計算函數<math>g: \mathbb N \to \mathbb N</math>，都存在時限<math>T(n)</math>，使得<math>\mathsf{DTIME}(g(T(n))) = \mathsf{DTIME}(T(n))</math>，其中[[DTIME]]表示[[圖靈機|確定性圖靈機]]在限時內能計算的函數的集合。

由於時限<math>T(n)</math>可以很大（且通常[[可構函數|不可構]]），間隙定理無法推出有關複雜度類<math>\mathsf{P}</math>或<math>\mathsf{NP}</math>的非平凡結果，<ref>{{citation|title=Computing Handbook, Third Edition: Computer Science and Software Engineering|trans-title=計算手冊，第三版：電腦科學與軟件工程|editor1-first=Teofilo|editor1-last=Gonzalez|editor2-first=Jorge|editor2-last=Diaz-Herrera|editor3-first=Allen|editor3-last=Tucker|publisher=CRC Press|year=2014|isbn=9781439898529|contribution=Chapter 7: Complexity Theory|first1=Eric W.|last1=Allender|first2=Michael C.|last2=Loui|first3=Kenneth W.|last3=Regan|page=7–9|url=https://books.google.com/books?id=vMqSAwAAQBAJ&pg=SA7-PA9|quote=Fortunately, the gap phenomenon cannot happen for time bounds ''t'' that anyone would ever be interested in|language=en|accessdate=2021-08-09|archive-date=2021-09-06|archive-url=https://web.archive.org/web/20210906215648/https://books.google.com/books?id=vMqSAwAAQBAJ&pg=SA7-PA9|dead-url=no}}.</ref>也不與[[時間階層定理]]或[[空間階層定理]]矛盾。<ref>{{citation|title=Computational Complexity: A Quantitative Perspective|trans-title=計算複雜度：定量觀點|volume=196|series=North-Holland Mathematics Studies|first=Marius|last=Zimand|publisher=Elsevier|year=2004|isbn=9780080476667|page=42|url=https://books.google.com/books?id=j-nhMYoZhgYC&pg=PA42|language=en|accessdate=2021-08-09|archive-date=2021-09-04|archive-url=https://web.archive.org/web/20210904224134/https://books.google.com/books?id=j-nhMYoZhgYC&pg=PA42|dead-url=no}}.</ref>

== 證明 ==
鮑羅丁<ref name="Bor72"/>證明的關鍵是，函數<math>t</math>在不同自然數的取值<math>t(n)</math>可以逐一選取，迫使所有複雜度<math>\Phi_i</math>都不能介乎<math>t</math>和<math>g \circ t</math>之間。具體而言：
*定義<math>t(0) = 1</math>；
*對<math>n \ge 1</math>，定義<math>t(n)</math>為最小的自然數<math>k</math>，使得<math>k > t(n-1)</math>，且對所有<math>i \le n</math>，有<math>\Phi_i(n) < k</math>或<math>\Phi_i(n) > g(k)</math>。

首先，由於<math>\Phi</math>滿足[[布盧姆公理]]，<math>\Phi_i(n) < k</math>和<math>\Phi_i(n) > g(k)</math>兩者皆是可判定的，故上述定義是<math>t</math>的<math>\mu</math>-[[遞歸函數|遞歸定義]]，從而<math>t</math>為（偏）可計算函數。

然後，為驗證<math>t</math>是全函數，需證明在定義<math>t(n)</math>時，滿足條件的<math>k</math>存在。對每個<math>i \le n</math>，
# 若<math>\Phi_i(n) = \infty</math>，則<math>\Phi_i(n) > g(k)</math>總成立；
# 否則，希望<math>\Phi_i(n) < k</math>成立。
所以只要<math>k</math>大於<math>\Phi_0(n),\ \Phi_1(n),\ \ldots,\ \Phi_n(n)</math>之中有限的全部數便可。故有<math>t</math>全可計算。

最後，由<math>t</math>的定義知，<math>t</math>遞增，且對每個<math>i</math>，當<math>n \ge i</math>時，或有<math>\Phi_i(n) < t(n)</math>，或有<math>\Phi_i(n) > g(t(n))</math>，故[[編號 (可計算性理論)|編號]]為<math>i</math>的可計算函數的複雜度不能介於<math>t</math>和<math>g \circ t</math>之間。

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

由此可見，没有程式的複雜度在<math>t</math>和<math>g \circ t</math>之間。雖然能用複雜度<math>g \circ t</math>和複雜度<math>t</math>實現的程式的集合是一樣的，但這只對某些的充分大的<math>t</math>成立。因此，間隙定理與[[布盧姆加速定理|加速定理]]不同。<ref>{{cite book|last=Borodin|first=Allan B.|title= Computational Complexity and the Existence of Complexity Gaps|trans-title =計算複雜度與複雜度間隙的存在性|date=1969|publisher=Cornell University|language = en}}</ref>

== 誠實性定理 ==
以不同的函數<math>t</math>為限，可以得到同一個複雜度類<math>\mathrm C(t)</math>。此種<math>t</math>稱為該複雜度類的'''名'''。[[時間階層定理]]和[[空間階層定理]]斷言，若限定複雜度類的名具有某種好性質（[[可構函數|可構]]），則不會有太大的間隙。對抽象複雜度而言，也有類似的性質，稱為'''誠實性'''（honestness）。以具有此種性質的函數為名的複雜度類之間，並無間隙現象。<ref>{{cite journal|author1=R.Moll|author2=A.R.Meyer|title=Honest Bounds for Complexity Classes of Recursive Functions|trans-title=遞歸函數複雜度類的誠實界|journal=Journal of Symbolic Logic|volume=39|issue=1|pages=127-138|date=1974 |language = en}}</ref>函數'''誠實'''是指其計算複雜度與輸入和輸出相比不太大（用詞源自「函數的值誠實反映其複雜度」）。麥克雷特（E. M. McCraight）和邁耶（A. R. Meyer）證明，以可計算函數為名的複雜度類，總能改名為誠實函數，而不改變其實質。所以，間隙定理的實際源由，是複雜度類改壞名。<ref>{{cite journal|author1=E. M. McCreight|author2=A. R. Meyer|title=Classes of computable functions defined by bounds on computation: preliminary report|trans-title=由計算的限制定義的可計算函數類：初步報告|journal=Proceedings of the first annual ACM symposium on Theory of computing|pages=79-88|date=1969 |language = en}}</ref>{{rp|86}}

== 算子間隙定理 ==
以<math>\mathcal{P}^{(1)}</math>表示（一元）可計算偏函數的類。映射<math>F:\mathcal{P}^{(1)}\to \mathcal{P}^{(1)}</math>稱為'''可（有效）計算算子'''，若存在全可計算函數<math>S</math>，使得<math>F \varphi_{e} = \varphi_{S(e)}</math>對所有<math>e</math>成立。此處<math>\varphi_e</math>是[[編號 (可計算性理論)|編號]]為<math>e</math>的函數。若<math>F</math>將全函數映至全函數，則稱<math>F</math>'''保全'''。間隙定理可複述成：對於由<math>Gf = g \circ f</math>定義的可計算保全算子<math>G</math>，可找到<math>t</math>令<math>t</math>和<math>Gt</math>之間有間隙。{{le|羅伯特·李·康斯特勃|Robert Lee Constable}}<!--按[[約翰·康斯特勃]]的先例-->證明，同樣的結論對其他可計算保全算子也成立，即：<ref>{{cite journal|author=Robert L. Constable|title=The operator gap|trans-title=算子間隙|journal=IEEE Conference Record of 10th Annual Symposium on Switching and Automata Theory|pages=20-26|date=1969 |language = en}}</ref>
:設<math>\Phi</math>為抽象複雜度衡量，則對任意滿足<math>Ff \ge f</math>的可計算保全算子<math>F</math>，存在嚴格遞增的可計算全函數<math>t</math>，令以<math>t</math>和<math>F t</math>為限的程式編號集相等。

== 參見 ==

*[[布盧姆加速定理]]

== 參考資料 ==
{{Reflist}}

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