首页
随机
附近
登录
设置
资助维基百科
关于维基百科
免责声明
搜索
User
:
Bluedecklibrary/Template:复杂度类
语言
监视
编辑
<
User:Bluedecklibrary
查
论
编
重要的
複雜度類
(
完整列表
)
易解复杂度类
DLOGTIME
·
AC
0
(
英语
:
AC0
)
·
ACC
0
(
英语
:
ACC0
)
·
L
·
SL
·
RL
·
NL
·
NC
(
英语
:
NC (complexity)
)
·
SC
·
P
(
P-完全
) ·
ZPP
·
RP
·
BPP
·
BQP
·
PolyL
怀疑难解复杂度类
UP
·
NP
(
NP完全
·
NP困难
·
反NP
·
反NP完全
(
英语
:
co-NP-complete
)
) ·
AM
(
英语
:
Arthur–Merlin protocol
)
·
PH
·
PP
·
#P
(
#P-完全
(
英语
:
Sharp-P-complete
)
) ·
IP
·
PSPACE
(
PSPACE完全
(
英语
:
PSPACE-complete
)
)
难解复杂度类
EXPTIME
·
NEXPTIME
·
EXPSPACE
·
ELEMENTARY
·
PR
·
R
·
RE
·
ALL
复杂度类的谱系
多项式谱系
(
英语
:
Polynomial hierarchy
)
·
指數譜系
·
Grzegorczyk谱系
(
英语
:
Grzegorczyk hierarchy
)
·
算术谱系
相关复杂度族
DTIME
·
NTIME
·
DSPACE
(
英语
:
DSPACE
)
·
NSPACE
·
可能性核对证明
(
英语
:
Probabilistically checkable proof
)
·
交互式证明系统
Bluedecklibrary/Template:复杂度类