複雑性クラス
P - 多項式時間で解ける問題のクラス
P完全 - P の中で最も難しい問題のクラスであり、並列コンピュータで解ける
PH - 多項式階層にあるクラス群の和集合
PP - 確率的に多項式時間で解ける問題のクラス(解が正しい可能性は2分の1より若干大きい)
PR - 原始再帰関数で解ける問題のクラス
PSPACE - 多項式領域で解ける問題のクラス
PSPACE完全 - PSPACE の中で最も難しい問題群
R - 有限時間で解ける問題のクラス。つまり、チューリングマシンで解ける全問題の集合であり、帰納言語に相当
RE - "YES" ならば停止し、"NO" ならば停止しないチューリングマシンの存在する問題のクラス。すなわち、帰納的可算言語に相当。これはまた解に対して witness が存在し、解の候補と witness が与えられたとき検証がチューリングマシンで解ける問題のクラスに一致する
RP - 乱択アルゴリズムで多項式時間で解ける問題のクラス(解がNOの場合は正しくない可能性があるが、YESなら正しい)
UP - 非決定性チューリングマシンで多項式時間で解ける決定問題のクラス(PとNPの中間)
ZPP - 乱択アルゴリズムで解ける問題のクラス(解は常に正しいが、平均で多項式時間かかる)