結構複雜度理論

维基百科，自由的百科全书

在計算複雜度理論內，結構複雜度理論（英語：structural complexity theory)或者簡單的結構複雜度（英語：structural complexity)是專門研究複雜度類本身，而非單一問題的可計算性或演算法的學問。這理論牽涉到研究各種複雜度類的內部結構以及不同複雜度類之間的關係。[1]

這理論的出現，是在解決這類問題中第一個，也仍是最重要的一個問題：P/NP問題時，不斷失敗的一個結果。許多這方面的研究都基於 P != NP這個假設，以及一個更深遠的推測：多項式時間譜系內的複雜度類個數是無限的。[1]

這個領域的一些主要研究方向有：[1]

  • 各種未解的問題，對複雜度類之間關係所產生的影響。
  • 各種限制資源的歸約方式以及相對應的完全語言。
  • 各種對於讀取跟儲存資料的限制以及使用方法，會對複雜度類產生的影響。

相關條目[编辑]

參考資料[编辑]

  1. ^ 1.0 1.1 1.2 Juris Hartmanis, "New Developments in Structural Complexity Theory" (invited lecture), Proc. 15th International Colloquium on Automata, Languages and Programming, 1988 (ICALP 88), Lecture Notes in Computer Science, vol. 317 (1988), pp. 271-286.
取自“https://zh.wikipedia.org/w/index.php?title=結構複雜度理論&oldid=36412509”