複雜度類列表

此條目介紹的是計算複雜度理論內的複雜度類列表。关于其他的可計算性理論和計算複雜度理論的主題，请见「可計算理論與複雜度理論列表」。

許多複雜度類都有一個前面加上'Co'的同伴，這是包含原來複雜度類裡面所有問題的補集的一個複雜度類。像是，若一個語言屬於NP，則此語言的補集則屬於Co-NP。（注意這裡不代表NP的補集就等同於Co-NP - 有一些語言同時是NP也是Co-NP，也有語言兩者皆非。）

一個複雜度類裡面"最難的問題"代表這個複雜度類裡面所有的問題都可以歸約為這個問題。此外，歸約過程本身是這個複雜度或者比他更簡單的問題類別裡面。

如果找不到想要看的複雜度類（例如說找不到Co-UP），那可以尋找看看這一個類別的同伴（以剛剛的例子來說：UP）來參考。

#P	計算NP問題的解答個數
#P-完全	#P問題裡面最難的問題集合
2-EXPTIME	在雙指數時間內可以解決
AC0	一個有限制深度的線路複雜度類。
AC	一種線路複雜度類
AH	算術階層（arithmetic hierarchy）的複雜度類
AP	使用交替式圖靈機在多項式時間之內可以解決的問題[1]
AM	以亞瑟梅林協定在多項式時間內可以解決的問題[1]
BPL	隨機演算法在多項式時間與對數空間內可以解答的問題集合（解答或許不正確）
BPP	隨機演算法在多項式時間內可以解答的問題集合（解答或許不正確）
BQP	量子電腦在多項式時間內可以解答的問題集合（解答或許不正確）
反NP	使用非決定型圖靈機可以在多項式時間內檢查輸出將為"NO"的問題
反NP完全	Co-NP問題裡面最難的問題集合
DSPACE(f(n))	使用決定型圖靈機在O(f(n))空間裡面可以解決的問題
DTIME(f(n))	使用決定型圖靈機在O(f(n))時間裡面可以解決的問題
E	可以用指數時間，在線性指數之下，解決的問題
ELEMENTARY	在指數層級（exponential hierarchy）裡面所有複雜度類的聯集
ESPACE	可以用指數空間，在線性指數之下，解決的問題
EXP	EXPTIME的另一種稱呼
EXPSPACE	在指數大小空間內可以解決的問題
EXPTIME	在指數大小時間內可以解決的問題
FNP	相類於NP的功能性問題版本
FP	相類於P的功能性問題版本
FP^NP	P^NP的功能性問題版本，又名NP-易；有名的旅行推銷員問題屬於這一類
IP	使用交互式證明系統可在多項式時間內解決的問題
L	可以在對數（小）空間內解決的問題
LOGCFL	可以在對數空間內歸約為上下文無關語言
MA	使用梅林亞瑟協定在多項式時間內可以解決的問題
NC	用平行電腦可以有效率（換句話說，在多項式對數時間，polylogarithmic time，之內）解決的問題
NE	可以用指數時間，在線性指數之下使用非確定型圖靈機解決的問題
NESPACE	可以用指數空間，在線性指數之下使用非確定型圖靈機解決的問題
NEXP	NEXPTIME的別名
NEXPSPACE	使用非決定型圖靈機在指數空間內可以解決的問題
NEXPTIME	使用非決定型圖靈機在指數時間內可以解決的問題
NL	正確的解答可以在對數時間內被檢查完畢
NONELEMENTARY	ELEMENTARY的補集
NP	正確的解答可以在多項式時間內被檢查完畢（參見複雜度類P與NP的關係）
NP-完全	NP裡面最難的問題集合
NP-易（或稱NP-容易）	FP^NP的別名
NP-等價	FP^NP裡面最難的問題，同時是NP-易也是NP-難的問題
NP困难	NP-完全或者更難的問題
NSPACE(f(n))	以O(f(n))這麼多空間使用非決定型圖靈機可以解決的問題
NTIME(f(n))	以O(f(n))這麼多時間使用非決定型圖靈機可以解決的問題
P	以多項式時間使用一般圖靈機可以解決的問題
P-完全	在P複雜度裡面，從平行電腦的角度看，最難解決的一類問題
PH	在polynomial hierarchy裡面所有類別的聯集
P^NP	使用一個可以解決一種NP問題的神諭，則可以在多項式時間內解決的問題；也叫做Δ2P
PP	概率多項式時間（答案有稍多於½的機會是正確的）
PSPACE	在多項式大小的記憶體內可以解決的問題
PSPACE-完全	PSPACE問題裡面最難的問題
R	有限時間內可以解決的問題
RE	若答案為"YES"我們在有限時間內可以知道，但是若答案為"NO"我們可能永遠算不出來的問題
RL	使用隨機演算法在對數大小空間內可以解決的問題（回答"NO"時有機會出錯，回答"YES"時一定是對的）
RP	使用隨機演算法在多項式時間內可以解決的問題（回答"NO"時有機會出錯，回答"YES"時一定是對的）
UP	非模糊非決定型多項式時間的決定性問題
ZPP	以隨機演算法可以解決的問題（答案永遠正確，平均時間複雜度為多項式時間）

參考資料

1. Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press; 1 edition, 2009, ISBN 978-0521424264 

外部链接

• Complexity Zoo - list of over 400 complexity classes and their properties