复杂度类列表

此条目介绍的是计算复杂度理论内的复杂度类列表。关于其他的可计算性理论和计算复杂度理论的主题，请见“可计算理论与复杂度理论列表”。

许多复杂度类都有一个前面加上'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的功能性问题版本
FPNP	PNP的功能性问题版本，又名NP-易；有名的旅行推销员问题属于这一类
IP	使用交互式证明系统可在多项式时间内解决的问题
L	可以在对数（小）空间内解决的问题
LOGCFL	可以在对数空间内归约为上下文无关语言
MA	使用梅林亚瑟协定在多项式时间内可以解决的问题
NC	用平行电脑可以有效率（换句话说，在多项式对数时间，polylogarithmic time，之内）解决的问题
NE	可以用指数时间，在线性指数之下使用非确定型图灵机解决的问题
NESPACE	可以用指数空间，在线性指数之下使用非确定型图灵机解决的问题
NEXP	NEXPTIME的别名
NEXPSPACE	使用非决定型图灵机在指数空间内可以解决的问题
NEXPTIME	使用非决定型图灵机在指数时间内可以解决的问题
NL	正确的解答可以在对数时间内被检查完毕
NONELEMENTARY	ELEMENTARY的补集
NP	正确的解答可以在多项式时间内被检查完毕（参见复杂度类P与NP的关系）
NP-完全	NP里面最难的问题集合
NP-易（或称NP-容易）	FPNP的别名
NP-等价	FPNP里面最难的问题，同时是NP-易也是NP-难的问题
NP困难	NP-完全或者更难的问题
NSPACE(f(n))	以O(f(n))这么多空间使用非决定型图灵机可以解决的问题
NTIME(f(n))	以O(f(n))这么多时间使用非决定型图灵机可以解决的问题
P	以多项式时间使用一般图灵机可以解决的问题
P-完全	在P复杂度里面，从平行电脑的角度看，最难解决的一类问题
PH	在polynomial hierarchy里面所有类别的联集
PNP	使用一个可以解决一种NP问题的神谕，则可以在多项式时间内解决的问题；也叫做Δ2P
PP	概率多项式时间（答案有稍多于½的机会是正确的）
PSPACE	在多项式大小的记忆体内可以解决的问题
PSPACE-完全	PSPACE问题里面最难的问题
R	有限时间内可以解决的问题
RE	若答案为"YES"我们在有限时间内可以知道，但是若答案为"NO"我们可能永远算不出来的问题
RL	使用随机演算法在对数大小空间内可以解决的问题（回答"NO"时有机会出错，回答"YES"时一定是对的）
RP	使用随机演算法在多项式时间内可以解决的问题（回答"NO"时有机会出错，回答"YES"时一定是对的）
UP	非模糊非决定型多项式时间的决定性问题
ZPP	以随机演算法可以解决的问题（答案永远正确，平均时间复杂度为多项式时间）