複雜度類

在計算複雜度理論中，一個複雜度類指的是在考慮某種特定的計算資源時，由一群同類問題所構成的集合。^[1]時間和空間是最常見的兩種計算資源。

一般而言，一個複雜度類的定義需要具有三個要素：

欲研究問題之類型；
所用之計算模型；
所研究之計算資源的上界。

許多常見的複雜度類別皆是基於使用圖靈機解決決定性問題時所需時間或空間（主記憶體）的多少來定義的。例如，P類問題包含了所有可由確定型圖靈機在多項式時間內解決的問題。當然，也存在基於其他問題類型（如計數問題（：计数问题 (复杂度)）和函數問題）或計算模型（如概率圖靈機、互動式證明系統和布林電路（：布尔电路）和量子電腦）定義的複雜度類別。

許多複雜度類可為數學邏輯所描述刻劃，請見描述性複雜度（英語：descriptive complexity）。

布盧姆複雜度則不需實際抽象機器就可定義複雜度類。

背景

決定性問題

決定性問題可以被不嚴謹地定義為「所有可被描述為『是非問題』的問題」。比如，「給定正數 $x$ ，問 $x$ 是否能被3整除？」便是一個決定性問題。該例子中， $x$ 為輸入變數。對於每一個輸入 $x$ 來說，該問題的答案要麼是「是」，要麼是「否」。那些回答為「是」的 $x$ 被稱為「真實例」（英語：yes-instance），回答為「否」的 $x$ 被稱為「假實例」（英語：no-instance）。將所有真實例搜集為一個集合，即可得到與該問題的對應的語言——語言的本質上是字串的集合。每一個決定性問題都有它所對應的語言——事實上，每一個語言也定義了一個決定性問題：「對於輸入 $x$ ， $x$ 是否存在於這個語言中？」。

圖靈機

圖靈機（英語：Turing machine）是1936年由英國數學家艾倫·圖靈提出的一種理想化的計算模型。它的執行邏輯非常簡單，但其計算能力等價於任何有限的數學邏輯過程。邱奇-圖靈論題認為任何有效演算法都可被某一個圖靈機實現。通俗地說，任何演算法都可以被視為一台圖靈機。這也意味着，如果某一問題不能被任何圖靈機解決，則該問題亦不能被任何演算法解決。對於任意輸入，圖靈機可能「接受」（輸出「真」）或「拒絕」（輸出「否」），但也有可能進入無窮迴圈，永遠不停機給出答案。

重要的複雜度類別

不可判定問題

某些決定性問題不能被任何單一固定的圖靈機解決，這類問題被稱為不可判定問題或不可判定語言（英語：Undecidable languages）。其中最著名的是停機問題^{[註 1]}，即判斷一個給定的圖靈機 $M$ 將一個給定的字串 $w$ 作為輸入執行時，是否能在有限步內停機。不可判定問題的語言必定是無窮大的——否則，可以直接羅列其中的所有字串，一一與輸入字串比較，即得到一個判定之的圖靈機。

RE與反RE

RE類問題是一類能被圖靈機部分解決的問題。其可被定義為：對於某一決定性問題 $L$ ，如果存在一個圖靈機 $M$ 滿足：輸入任何 $L$ 的真實例時， $M$ 停機並回答「是」；且輸入任何 $L$ 的假實例時， $M$ 不回答「是」（允許不停機），則 $L$ 屬於RE。

RE的名稱源於該類的英語名稱 Recursively Enumerable，即「遞歸可列舉」。該名稱來源於它基於列舉元的一個等價定義。

反RE問題，或co-RE，是另一類能被圖靈機部分解決的問題。它包含所有屬於RE的語言的補集。將上述RE類問題的定義中的「真實例」與「假實例」互換，即得到反RE的定義。

RE與反RE的交集R被稱為可判定問題（英語：Decidable problems）或遞歸語言（英語：Recursive languages）。不在R中的問題都被稱為不可判定問題。

P

P類問題，或稱多項式時間問題，是指能被某一圖靈機於多項式時間內解決的問題的集合。P是 Polynomial 的縮寫。許多一般意義上的「簡單」計算問題皆屬於P。例如判斷某數是否為另兩個數的最大公因數、最大匹配（：最大匹配）問題等。2002年發現質數的判定問題也屬於P^[2] 。P類問題被認為是一類「簡單問題」。事實上，Cobham猜想（：Cobham猜想）認為，P類問題是僅有的「有可能被實際解決的問題」。

NP

NP類問題，或稱非確定性多項式時間問題，是指能被某一非確定性圖靈機於多項式時間內解決的問題的集合。NP是 Nondeterministic Polynomial 的縮寫。

根據定義，所有P問題都屬於NP——直接將非確定性圖靈機當作普通圖靈機使用即可。另外，許多常見的難解問題都屬於NP，例如旅行推銷員問題的決定性問題版本、圖論中的分團問題等^{[註 2]}，但尚不清楚這些問題是否其實亦屬於P。即，尚未證明圖靈機的非確定性在解決這些問題時確實必要。這便是著名的P/NP問題。

PSPACE

PSPACE類問題是指所有能被圖靈機在多項式空間內所解決的問題的集合。直覺上，由於空間可以重複利用，而時間不能，因而會比只能利用多項式時間的P類問題包含更多、更複雜的問題。可以證明P和NP均包含於PSPACE，但判定該包含關係是否為真包含的問題尚未得到解決。

有類似NP之於P定義的，將定義中確定性圖靈機替換為非確定性圖靈機而得到的NPSPACE類。然而，根據薩維奇定理，NPSPACE = PSPACE，這意味着非確定性對於空間來說並不能對如同時間般有效地來降低開銷。

許多較為簡單的桌遊的優勝問題（即判定某一玩家是否有必勝策略的問題），如推廣版本的井字棋和接龍遊戲皆屬於PSPACE^{[註 3]}。直覺上，這是因為只需要線性的空間就可以模擬出棋盤上的所有可能的變局，同時遊戲的總的可能步數維持在棋盤格子數的多項式數量之內。

EXPTIME與NEXPTIME

EXPTIME類問題是指所有能被圖靈機在指數時間內所解決的問題的集合。PSPACE $\subseteq$ EXPTIME，這是因為圖靈機在多項式空間上僅有指數多種不同的格局，因此雖然沒有明文規定PSPACE圖靈機的執行時間上限，它們依然隱含一個指數的時間上限，執行時間超過該上限之後便可判定為進入無窮迴圈。

另外，根據時間階層定理，可以確認有P $\subsetneq$ EXPTIME。

一些更複雜的桌遊的優勝問題，如推廣版本的國際象棋和國際跳棋皆屬於EXPTIME^{[註 4]}。與井字棋等簡單桌遊不同，國際象棋等遊戲的步數數量隨着棋盤的擴大呈現指數級增長。

類似NP之於P，可以類似地定義NEXPTIME類問題。目前，同樣僅能確認EXPTIME $\subseteq$ NEXPTIME。不過如果P = NP，則有EXPTIME = NEXPTIME。

根據時間階層定理，可以確認有NP $\subsetneq$ NEXPTIME。

EXPSPACE

類似EXPTIME之於P，EXPSPACE之於PSPACE擁有了更多的可用空間——它是所有能被圖靈機在指數空間內所解決的問題的集合。比如判斷兩個正則表達式是否能生成同樣的語言就屬於EXPSPACE^{[註 5]}。

根據空間階層定理，可以確認有PSPACE $\subsetneq$ EXPSPACE。

複雜度類之間的關係

下表簡列了一些屬於複雜度理論的問題（或語言、文法等）類別。如果類別X是類別Y的子集合，則X將會畫在Y底下，並以一黑線相連。如果X是子集合，但不知是否與Y相等，則以較輕的虛線相連。實際上可解與不可解問題更屬於可計算性理論，但是它有助於更透徹了解複雜度類的問題。

擴充閱讀

複雜度類大觀園（頁面存檔備份，存於互聯網檔案館）：一個巨大的複雜度類列表，專家級使用。
複雜度類架構圖，由Neil Immerman（英語：Neil Immerman）製作，展示複雜度類的階層架構與它們是如何定位的。
Garey, Michael R.（英語：Michael Garey）與David S. Johnson（英語：David S. Johnson）: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. NP-complete（NPC問題是解決某些數學難題的重要關鍵，這問題暗示人們是否可以將某些演算法的執行效率提升到可接受的範圍）問題的標準指南。

註解

^ 特別地，停機問題亦屬於RE類問題
^ 更嚴格地來說，它們屬於NP完全
^ 更嚴格地來說，它們屬於PSPACE完全
^ 更嚴格地來說，它們屬於EXPTIME完全
^ 更嚴格地來說，它屬於EXPSPACE完全

參見

複雜度類列表

^ Johnson (1990).
^ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.

[2] 特別地，停機問題亦屬於RE類問題

[4] 更嚴格地來說，它們屬於NP完全

[5] 更嚴格地來說，它們屬於PSPACE完全

[6] 更嚴格地來說，它們屬於EXPTIME完全

[7] 更嚴格地來說，它屬於EXPSPACE完全

[FOOTNOTEJohnson1990-1] Johnson (1990).

[3] Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.

[1]

[註 1]

[2]

[註 2]

[註 3]

[註 4]

[註 5]