复杂度类

在计算复杂度理论中，一个复杂度类指的是在考虑某种特定的计算资源时，由一群同类问题所构成的集合。^[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]