首页
随机
附近
登录
设置
资助维基百科
关于维基百科
免责声明
搜索
模板
:
复杂度类
语言
监视
查
论
编
重要的
复杂度类
(
完整列表
)
易解复杂度类
对数空间
相关
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
)
交互式证明系统
量子复杂性理论