計算複雑性クラス
#計算複雑性理論
基礎クラス
決定性TM
DTIME
SPACE
TimeSpace
非決定性TM
NTIME
NSPACE
回路
SIZE
乱択計算
RTIME
BTIME
ZTIME
主要なクラス
LinTime
NLinTime
線形時間階層
LinH
L
NL
=
coNL
P
NP
coNP
E
多項式階層
PH
PSPACE
=
NPSPACE
EXP
NEXP
AC
NC
ZPP
RP
coRP
BPP