結構複雜度理論

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

基本介紹

• 中文名：結構複雜度理論
• 外文名：structural complexity theory

簡介

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

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

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

計算複雜性理論

計算複雜性理論（Computational complexity theory）是理論計算機科學和數學的一個分支，它致力於將可計算問題根據它們本身的複雜性分類，以及將這些類別聯繫起來。一個可計算問題被認為是一個原則上可以用計算機解決的問題，亦即這個問題可以用一系列機械的數學步驟解決，例如算法。

如果一個問題的求解需要相當多的資源（無論用什麼算法），則被認為是難解的。計算複雜性理論通過引入數學計算模型來研究這些問題以及定量計算解決問題所需的資源（時間和空間），從而將資源的確定方法正式化了。其他複雜性測度同樣被運用，比如通信量（套用於通信複雜性），電路中門的數量（套用於電路複雜性）以及中央處理器的數量（套用於並行計算）。計算複雜性理論的一個作用就是確定一個能或不能被計算機求解的問題的所具有的實際限制。

在理論計算機科學領域，與此相關的概念有算法分析和可計算性理論。兩者之間一個關鍵的區別是前者致力於分析用一個確定的算法來求解一個問題所需的資源量，而後者則是在更廣泛意義上研究用所有可能的算法來解決相同問題。更精確地說，它嘗試將問題分成能或不能在現有的適當受限的資源條件下解決這兩類。相應地，在現有資源條件下的限制正是區分計算複雜性理論和可計算性理論的一個重要指標：後者關心的是何種問題原則上可以用算法解決。

複雜性類

在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下形式：

• 可以被同一個抽象機器M使用O(f(n))的資源R所解決的問題的集合（n是輸入數據的大小）。
  

例如NP類別就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類別則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題的集合，例如FP。

許多複雜度類可被描述它的數學邏輯特徵化，請見可描述的複雜度。

而Blum公理用於不需實際計算模型就可定義複雜度類的情況。