時間階層定理
在計算複雜度理論內，時間階層定理（Time hierarchy theorems）是一個有關圖靈機時間限制上面一系列重要的定理。用不大正式的說法解釋，這理論告訴我們圖靈機在給予更多時間之後，保證能解決更多的問題。 舉例：必然存在問題是圖靈機可以用n2的時間解決，但是不能用n的時間解決。 參考資料 Pages 310–313 of section 9.1: Hierarchy theorems. Section 7.2: The Hier…
标签：#結構複雜度理論
共 4 篇文章
萨维奇定理
萨维奇定理（）是计算复杂性理论中的一个定理，由于1970年证明。定理的结论为对于任何函数f(n)满足f(n)\geq \log n，下列关系成立： :\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right). 亦即，如果一台非确定型图灵机能够利用f(n)空间解决某个问题，那么一台…
結構複雜度理論
在計算複雜度理論內，結構複雜度理論（)或者簡單的結構複雜度（)是專門研究複雜度類本身，而非單一問題的可計算性或演算法的學問。這理論牽涉到研究各種複雜度類的內部結構以及不同複雜度類之間的關係。 這理論的出現，是在解決這類問題中第一個，也仍是最重要的一個問題：P/NP問題時，不斷失敗的一個結果。許多這方面的研究都基於 P != NP這個假設，以及一個更深遠的推測：多項式時間譜系內的複雜度類個數是無限的。 這個領域的一些主要研究方向有： 各種…
布盧姆公理
布魯姆公理（英語：Blum Axioms），或稱布魯姆複雜度公理（英語：Blum Complexity Axioms），是計算複雜性理論中，定義可計算函數的複雜度時，應滿足的條件。這些公理最先由曼紐爾·布魯姆於1967年提出。 重要的是，只要複雜度衡量滿足這些公理，布盧姆加速定理和間隙定理就成立。滿足這些公理的複雜度衡量裡，最有名的是有關時間（見時間複雜度）和空間（見空間複雜度）的複雜度。 定義 布魯姆複雜度衡量是一個二元組(\varp…