複雜度類

在計算複雜度理論中，一個複雜度類指的是在考虑某种特定的计算资源时，由一群同类問題所构成的集合。^[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]