查看“︁複雜度類”︁的源代码

{{NoteTA
|G1 = IT
}}
在[[計算複雜度理論]]中，一個'''複雜度類'''指的是在考虑某种特定的计算资源时，由一群同类問題所构成的[[集合 (数学)|集合]]。{{sfnp|Johnson|1990}}[[时间复杂度|时间]]和[[空间复杂度|空间]]是最常见的两种计算资源。

一般而言，一个複雜度類的定义需要具有三个要素：
# 欲研究问题之类型；
# 所用之[[计算模型 (数学)|计算模型]]；
# 所研究之计算资源的上界。

许多常见的复杂度类皆是基于使用[[图灵机]]解决[[决定性问题]]时所需时间或空间（[[電腦記憶體|内存]]）的多少来定义的。例如，[[P (复杂度)|'''P''']]类问题包含了所有可由确定型图灵机在[[多项式时间]]内解决的问题。当然，也存在基于其他问题类型（如{{Tsl|Counting problem (complexity)|计数问题 (复杂度)|计数问题}}和[[函数问题]]）或计算模型（如[[概率图灵机]]、[[交互式证明系统]]和{{Tsl|Boolean circuit|布尔电路}}和[[量子计算机]]）定义的复杂度类。

許多複雜度類可為[[數學邏輯]]所描述刻劃，請見{{Link-en|描述性複雜度|descriptive complexity}}。

[[布盧姆公理|布盧姆複雜度]]則不需實際[[計算模型 (數學)|抽象機器]]就可定義複雜度類。

== 背景 ==
=== 决定性问题 ===
{{main|决定性问题}}

决定性问题可以被不严谨地定义为“所有可被描述为‘是非问题’的问题”。比如，“给定正数 <math>x</math>，问 <math>x</math> 是否能被3整除？”便是一个决定性问题。该例子中，<math>x</math> 为输入变量。对于每一个输入 <math>x</math> 来说，该问题的答案要么是“是”，要么是“否”。那些回答为“是”的 <math>x</math> 被称为“真实例”（{{lang-en|yes-instance}}），回答为“否”的 <math>x</math> 被称为“假实例”（{{lang-en|no-instance}}）。将所有真实例搜集为一个集合，即可得到与该问题的对应的'''语言'''——语言的本质上是字符串的集合。每一个决定性问题都有它所对应的语言——事实上，每一个语言也定义了一个决定性问题：“对于输入 <math>x</math>，<math>x</math> 是否存在于这个语言中？”。

=== 图灵机 ===
{{main|图灵机}}

图灵机（{{lang-en|Turing machine}}）是1936年由[[英国]][[数学家]][[艾倫·图灵]]提出的一种理想化的[[计算模型]]。它的运行逻辑非常简单，但其计算能力等价于任何有限的数学逻辑过程。[[邱奇-图灵论题]]认为任何有效算法都可被某一个图灵机实现。通俗地说，任何算法都可以被视为一台图灵机。这也意味着，如果某一问题不能被任何图灵机解决，则该问题亦不能被任何算法解决。对于任意输入，图灵机可能“接受”（输出“真”）或“拒绝”（输出“否”），但也有可能进入死循环，永远不停机给出答案。

== 重要的复杂度类 ==
{{main|复杂度类列表}}

=== 不可判定问题 ===
{{main|不可判定问题}}

某些决定性问题不能被任何单一固定的图灵机解决，这类问题被称为'''不可判定问题'''或'''不可判定语言'''（{{lang-en|Undecidable languages}}）。其中最著名的是[[停机问题]]{{NoteTag|特别地，停机问题亦属于'''RE'''类问题}}，即判断一个给定的图灵机 <math>M</math> 将一个给定的字符串 <math>w</math> 作为输入运行时，是否能在有限步内停机。不可判定问题的语言必定是无穷大的——否则，可以直接罗列其中的所有字符串，一一与输入字符串比较，即得到一个判定之的图灵机。

=== RE与反RE ===
{{main|RE (复杂度)}}

'''RE'''类问题是一类能被图灵机''部分解决''的问题。其可被定义为：对于某一决定性问题 <math>L</math>，如果存在一个图灵机 <math>M</math> 满足：输入任何 <math>L</math> 的真实例时， <math>M</math> 停机并回答“是”；且输入任何 <math>L</math> 的假实例时， <math>M</math> 不回答“是”（允许不停机），则 <math>L</math> 属于'''RE'''。

'''RE'''的名称源于该类的英语名称 '''R'''ecursively '''E'''numerable，即“递归可枚举”。该名称来源于它基于枚举器的一个等价定义。

'''反RE'''问题，或'''co-RE'''，是另一类能被图灵机部分解决的问题。它包含所有属于'''RE'''的语言的补集。将上述'''RE'''类问题的定义中的“真实例”与“假实例”互换，即得到'''反RE'''的定义。

'''RE'''与'''反RE'''的交集'''R'''被称为'''可判定问题'''（{{lang-en|Decidable problems}}）或'''[[递归语言]]'''（{{lang-en|Recursive languages}}）。不在'''R'''中的问题都被称为不可判定问题。

=== P ===
{{main|P (复杂度)}}
'''P'''类问题，或称'''多项式时间问题'''，是指能被某一[[图灵机]]于[[多项式时间]]内解决的问题的集合。'''P'''是 '''P'''olynomial 的缩写。许多一般意义上的“简单”计算问题皆属于'''P'''。例如判断某数是否为另两个数的[[最大公因数]]、{{Tsl|Maximum cardinality matching|最大匹配}}问题等。2002年发现[[质数]]的判定问题也属于'''P'''<ref>Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "[http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf PRIMES is in P] {{Wayback|url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |date=20171207171714 }}", ''Annals of Mathematics'' 160 (2004), no. 2, pp. 781–793.</ref> 。'''P'''类问题被认为是一类“简单问题”。事实上，{{Tsl|Cobham's thesis||Cobham猜想}}认为，'''P'''类问题是仅有的“有可能被实际解决的问题”。

=== NP ===
{{main|NP (复杂度)}}

'''NP'''类问题，或称'''非确定性多项式时间问题'''，是指能被某一''非确定性''图灵机于多项式时间内解决的问题的集合。'''NP'''是 '''N'''ondeterministic '''P'''olynomial 的缩写。

根据定义，所有'''P'''问题都属于'''NP'''——直接将非确定性图灵机当作普通图灵机使用即可。另外，许多常见的难解问题都属于'''NP'''，例如[[旅行推销员问题]]的决定性问题版本、图论中的[[分团问题]]等{{NoteTag|更严格地来说，它们属于[[NP完全]]}}，但尚不清楚这些问题是否其实亦属于'''P'''。即，尚未证明图灵机的非确定性在解决这些问题时确实必要。这便是著名的[[P/NP问题]]。

=== PSPACE ===
{{main|PSPACE}}

'''PSPACE'''类问题是指所有能被图灵机在多项式''空间''内所解决的问题的集合。直觉上，由于空间可以重复利用，而时间不能，因而会比只能利用多项式时间的'''P'''类问题包含更多、更复杂的问题。可以证明'''P'''和'''NP'''均包含于'''PSPACE'''，但判定该包含关系是否为真包含的问题尚未得到解决。

有类似'''NP'''之于'''P'''定义的，将定义中确定性图灵机替换为非确定性图灵机而得到的'''NPSPACE'''类。然而，根据[[萨维奇定理]]，'''NPSPACE''' = '''PSPACE'''，这意味着非确定性对于空间来说并不能对如同时间般有效地来降低开销。

许多较为简单的桌游的优胜问题（即判定某一玩家是否有必胜策略的问题），如推广版本的[[井字棋]]和[[接龙 (文字游戏)|接龙游戏]]皆属于'''PSPACE'''{{NoteTag|更严格地来说，它们属于[[PSPACE完全]]}}。直觉上，这是因为只需要线性的空间就可以模拟出棋盘上的所有可能的变局，同时游戏的总的可能步数维持在棋盘格子数的多项式数量之内。

=== EXPTIME与NEXPTIME ===
{{main|EXPTIME}}

'''EXPTIME'''类问题是指所有能被图灵机在[[指数时间]]内所解决的问题的集合。'''PSPACE''' <math>\subseteq</math> '''EXPTIME'''，这是因为图灵机在多项式空间上仅有指数多种不同的[[图灵机#图灵机的基本术语|格局]]，因此虽然没有明文规定'''PSPACE'''图灵机的运行时间上限，它们依然隐含一个指数的时间上限，运行时间超过该上限之后便可判定为进入死循环。

另外，根据[[时间阶层定理]]，可以确认有'''P''' <math>\subsetneq</math> '''EXPTIME'''。

一些更复杂的桌游的优胜问题，如推广版本的[[国际象棋]]和[[国际跳棋]]皆属于'''EXPTIME'''{{NoteTag|更严格地来说，它们属于[[EXPTIME完全]]}}。与井字棋等简单桌游不同，国际象棋等游戏的步数数量随着棋盘的扩大呈现指数级增长。

{{main|NEXPTIME}}

类似'''NP'''之于'''P'''，可以类似地定义'''NEXPTIME'''类问题。目前，同样仅能确认'''EXPTIME''' <math>\subseteq</math> '''NEXPTIME'''。不过如果'''P''' = '''NP'''，则有'''EXPTIME''' = '''NEXPTIME'''。

根据[[时间阶层定理]]，可以确认有'''NP''' <math>\subsetneq</math> '''NEXPTIME'''。

=== EXPSPACE ===
{{main|EXPSPACE}}

类似'''EXPTIME'''之于'''P'''，'''EXPSPACE'''之于'''PSPACE'''拥有了更多的可用空间——它是所有能被图灵机在指数空间内所解决的问题的集合。比如判断两个[[正则表达式]]是否能生成同样的语言就属于'''EXPSPACE'''{{NoteTag|更严格地来说，它属于[[EXPSPACE完全]]}}。

根据[[空间阶层定理]]，可以确认有'''PSPACE''' <math>\subsetneq</math> '''EXPSPACE'''。

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

<table cellpadding="0" cellspacing="0" border="0" style="margin:auto;">
<tr style="text-align:center;">
<td colspan=2></td>
<td colspan=4><table cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"><tr><td style="text-align:center;">[[決定性問題]]</td></tr></table></td>
</tr>
<tr style="text-align:center;">
<td colspan=2></td>
<td>[[image:solidLine.png]]</td>
<td colspan=2></td>
<td>[[image:solidLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"><tr><td style="text-align:center;">[[递归可枚举语言|類型0（递归可枚举）]]</td></tr></table></td>
<td></td>
<td colspan=4><table cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:200%; height:200%;"><tr><td style="text-align:center;">[[未決定問題列表|未決定問題]]</td></tr></table></td>
</tr>
<tr style="text-align:center;">
<td colspan=3>[[image:solidLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"><tr><td style="text-align:center;">[[递归语言|递归]]</td></tr></table></td>
</tr>
<tr style="text-align:center;">
<td colspan=3>[[image:solidLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"><tr><td style="text-align:center;">[[EXPSPACE]]</td></tr></table></td>
</tr>
<tr style="text-align:center;">
<td colspan=3>[[image:dottedLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"><tr><td style="text-align:center;">[[NEXPTIME]]</td></tr></table></td>
</tr>
<tr style="text-align:center;">
<td colspan=3>[[image:dottedLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"><tr><td style="text-align:center;">[[EXPTIME]]</td></tr></table></td>
</tr>
<tr style="text-align:center;">
<td colspan=3>[[image:dottedLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td colspan=8><table cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"><tr><td style="text-align:center;">[[PSPACE]]</td></tr></table></td>
</tr>
<tr style="text-align:center;">
<td>[[image:solidLine.png]]</td>
<td width=40>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td><table cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"><tr><td style="text-align:center;">[[上下文有关语言|類型1（上下文有关）]]</td></tr></table></td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td border="1">[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td><table cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"><tr><td style="text-align:center;">[[反NP]]</td></tr></table></td>
<td><table cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"><tr><td style="text-align:center;">[[BQP]]</td></tr></table></td>
<td></td>
<td colspan=2><table cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"><tr><td style="text-align:center;">[[NP (複雜度)|NP]]</td></tr></table></td>
</tr>
<tr style="text-align:center;">
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td><table cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"><tr><td style="text-align:center;">[[BPP (複雜度)|BPP]]</td></tr></table></td>
<td width=10></td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td></td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td colspan=5><table cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"><tr><td style="text-align:center;">[[P (複雜度)|P]]</td></tr></table></td>
</tr>
<tr style="text-align:center;">
<td>[[image:solidLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
<td>[[image:dottedLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td>[[image:solidLine.png]]</td>
<td colspan=2><table cellpadding="0" cellspacing="0" border="1" style="background:lightGreen; width:100%; height:100%;"><tr><td style="text-align:center;">[[NC (複雜度)|NC]]</td></tr></table></td>
</tr>
<tr style="text-align:center;">
<td>[[image:solidLine.png]]</td>
<td colspan=2>[[image:solidLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"><tr><td style="text-align:center;">[[上下文无关语言|類型2（上下文无关）]]</td></tr></table></td>
</tr>
<tr style="text-align:center;">
<td colspan=3>[[image:solidLine.png]]</td>
</tr>
<tr style="text-align:center;">
<td colspan=3><table cellpadding="0" cellspacing="0" border="1" style="background:lightBlue; width:100%; height:100%;"><tr><td style="text-align:center;">[[正则语言|類型3（正则）]]</td></tr></table></td>
</tr>
</table>

== 擴充閱讀 ==
*[https://complexityzoo.net/Complexity_Zoo 複雜度類大觀園] {{Wayback|url=https://complexityzoo.net/Complexity_Zoo |date=20231110225207}}：一個巨大的複雜度類列表，專家級使用。
*[https://web.archive.org/web/20160416021243/https://people.cs.umass.edu/~immerman/complexity_theory.html 複雜度類架構圖]，由{{tsl|en|Neil Immerman|}}製作，展示複雜度類的階層架構與它們是如何定位的。
*{{tsl|en|Michael Garey||Garey, Michael R.}}與{{tsl|en|David S. Johnson|}}: ''Computers and Intractability: A Guide to the Theory of NP-Completeness.'' New York: W. H. Freeman & Co., 1979.  [[NP-complete]]（NPC問題是解決某些[[P/NP問題|數學難題]]的重要關鍵，這問題暗示人們是否可以將某些[[演算法]]的執行效率提升到可接受的範圍）問題的標準指南。

==注解==
{{noteFoot}}

==参见==
*[[複雜度類列表]]

{{-}}
{{ComplexityClasses}}

[[Category:複雜度類| ]]
[[Category:計算複雜性理論]]