多項式階層
Σ 0 P := Π 0 P := P {\displaystyle \Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\rm {P}}} Σ k + 1 P := ∃ P Π k P {\displaystyle \Sigma _{k+1}^{\rm {P}}:=\exists ^{\rm {P}}\Pi _{k}^{\rm {P}}} Π k + 1 P := ∀ P Σ k P {\displaystyle \Pi _{k+1}^{\rm {P}}:=\forall ^{\rm {P}}\Sigma _{k}^{\rm {P}}} なお、 N P = Σ 1 P {\displaystyle {\rm {NP}}=\Sigma _{1}^{\rm {P}}} であり、かつ c o N P = Π 1 P {\displaystyle {\rm {coNP}}=\Pi _{1}^{\rm {P}}} である。この定義は多項式階層と算術的階層の密接な関連を反映しており、後者で DEC と CE が果たした役割をそれぞれ P と NP が果たしている。同様の方法で、実数の部分集合の階層として解析的階層が定義される。
交替性チューリング機械を使った等価な定義として、 Σ k P {\displaystyle \Sigma _{k}^{\rm {P}}} (あるいは Π k P {\displaystyle \Pi _{k}^{\rm {P}}} )は存在的状態(あるいは全称的状態)から開始する交替性チューリング機械で k {\displaystyle k} 回の交替を行うことで多項式時間で解ける決定問題の集合と定義される。
例えば、 Σ 1 P = N P , Π 1 P = c o N P {\displaystyle \Sigma _{1}^{\rm {P}}={\rm {NP}},\Pi _{1}^{\rm {P}}={\rm {coNP}}} であり、 Δ 2 P = P N P {\displaystyle \Delta _{2}^{\rm {P}}={\rm {P^{NP}}}} は NP に属する何らかの問題を解く神託を備えることで多項式時間で解ける問題のクラスである。
多項式階層の存在/全称的定義のため、 L {\displaystyle L} を形式言語(すなわち、一種の決定問題であり、{0,1} の部分集合である)、 p {\displaystyle p} を多項式とし、次のように定義する。 ∃ p L := { x ∈ { 0 , 1 } ∗ | ( ∃ w ∈ { 0 , 1 } ≤ p ( | x | ) ) ⟨ x , w ⟩ ∈ L } , {\displaystyle \exists ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\exists w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\},} ここで、 ⟨ x , w ⟩ ∈ { 0 , 1 } ∗ {\displaystyle \langle x,w\rangle \in \{0,1\}^{*}} は2進文字列 x と w を1つの2進文字列にする何らかの標準的符号化である。