多項式階層
L は文字列の順序対の集合を表しており、第一の文字列 x は ∃ p L {\displaystyle \exists ^{p}L} の元で、第二の文字列 w は x が ∃ p L {\displaystyle \exists ^{p}L} の元であることを示す短い ( | w | ≤ p ( | x | ) {\displaystyle |w|\leq p(|x|)} ) 証拠である。言い換えれば、 x ∈ ∃ p L {\displaystyle x\in \exists ^{p}L} は、 ⟨ x , w ⟩ ∈ L {\displaystyle \langle x,w\rangle \in L} であるような短い証拠 w が存在することと同値である。同様に次のように定義する。 ∀ p L := { x ∈ { 0 , 1 } ∗ | ( ∀ w ∈ { 0 , 1 } ≤ p ( | x | ) ) ⟨ x , w ⟩ ∈ L } {\displaystyle \forall ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\forall w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\}} ドモルガンの定理により、 ( ∃ p L ) c = ∀ p L c {\displaystyle \left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}} かつ ( ∀ p L ) c = ∃ p L c {\displaystyle \left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}} であり、ここで L は L の補集合である。