多項式階層
多項式階層をなすクラス群の定義はいくつか存在する。
多項式階層は神託機械を使って次のように定義する。 Δ 0 P := Σ 0 P := Π 0 P := P , {\displaystyle \Delta _{0}^{\rm {P}}:=\Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\mbox{P}},} ここで、P は多項式時間内で解ける決定問題の集合である。i ≥ 0 については、次のように定義する。 Δ i + 1 P := P Σ i P {\displaystyle \Delta _{i+1}^{\rm {P}}:={\mbox{P}}^{\Sigma _{i}^{\rm {P}}}} Σ i + 1 P := NP Σ i P {\displaystyle \Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Sigma _{i}^{\rm {P}}}} Π i + 1 P := coNP Σ i P {\displaystyle \Pi _{i+1}^{\rm {P}}:={\mbox{coNP}}^{\Sigma _{i}^{\rm {P}}}} ここで、A はクラス A のチューリングマシンにクラス B の何らかの問題を解く神託を付加して強化したもので解ける決定問題の集合である。