結構複雜度理論
在計算複雜度理論內，結構複雜度理論（英語：structural complexity theory)或者簡單的結構複雜度（英語：structural complexity)是專門研究複雜度類本身，而非單一問題的可計算性或演算法的學問。這理論牽涉到研究各種複雜度類的內部結構以及不同複雜度類之間的關係。[1]
這理論的出現，是在解決這類問題中第一個，也仍是最重要的一個問題：P/NP問題時，不斷失敗的一個結果。許多這方面的研究都基於 P != NP這個假設，以及一個更深遠的推測：多項式時間譜系內的複雜度類個數是無限的。[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.