首页
随机
附近
登录
设置
资助维基百科
关于维基百科
免责声明
搜索
模板
:
复杂度类
语言
监视
编辑
查
论
编
重要的
复杂度类
（
完整列表
）
易解复杂度类
对数空间
相关
DLOGTIME
AC
0
（
英语
：
AC0
）
ACC
0
（
英语
：
ACC0
）
TC
0
（
英语
：
TC0
）
L ·
FL ·
SL ·
NL
NC
SC
PolyL
多项式空间
相关
P
（
P-完全
）
FP
（
英语
：
FP (complexity)
）
ZPP
RP
BPP
BQP
（
QMA
（
英语
：
QMA
）
PostBQP
（
英语
：
PostBQP
）
EQP
（
英语
：
EQP
）
）
怀疑难解复杂度类
UP
NP
（
NP完全
NP困难
反NP
反NP完全
（
英语
：
co-NP-complete
）
）
FNP
（
英语
：
FNP (complexity)
）
（
TFNP
（
英语
：
TFNP (complexity)
）
）
PH
PP
#P
（
#P-完全
（
英语
：
Sharp-P-complete
）
）
PSPACE
（
PSPACE完全
（
英语
：
PSPACE-complete
）
）
难解复杂度类
EXPTIME
NEXPTIME
EXPSPACE
ELEMENTARY
PR
R
RE
ALL
复杂度类的谱系
多项式谱系
指数谱系
Grzegorczyk谱系
（
英语
：
Grzegorczyk hierarchy
）
算术谱系
相关复杂度族
DTIME
NTIME
DSPACE
（
英语
：
DSPACE
）
NSPACE
可能性核对证明
（
英语
：
Probabilistically checkable proof
）
交互式证明系统
量子复杂性理论
