复杂度类列表

许多复杂度类都有一个前面加上'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 以随机算法可以解决的问题(答案永远正确,平均时间复杂度为多项式时间)

参考资料

  1. ^ 1.0 1.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