多項式階層
C M = { ⟨ A , k ⟩ ∈ C × N | there exists a circuit B with at most k gates such that A and B compute the same function } {\displaystyle CM=\left\{\langle A,k\rangle \in {\mathcal {C}}\times \mathbb {N} \left|{\begin{matrix}{\mbox{there exists a circuit }}B{\mbox{ with at most }}k{\mbox{ gates }}\\{\mbox{ such that }}A{\mbox{ and }}B{\mbox{ compute the same function}}\end{matrix}}\right.\right\}} L {\displaystyle L} が多項式時間で決定可能であり、かつ与えられた ⟨ A , k ⟩ {\displaystyle \langle A,k\rangle } について ⟨ A , k ⟩ ∈ C M {\displaystyle \langle A,k\rangle \in CM} であることと全ての入力 x {\displaystyle x} について ⟨ A , k , B , x ⟩ ∈ L {\displaystyle \langle A,k,B,x\rangle \in L} となる回路 B {\displaystyle B} が存在することは同値であることから、 C M ∈ Σ 2 P ( = ∃ P ∀ P P ) {\displaystyle CM\in \Sigma _{2}^{P}(=\exists ^{\rm {P}}\forall ^{\rm {P}}{\rm {P}})} が成り立つ。
Σ 2 P {\displaystyle \Sigma _{2}^{P}} に属する問題の具体例として「回路最小化」問題がある。ある数 k とブール関数 f を計算する回路 A があるとき、同じ関数 f を最大 k 個の論理ゲートで計算できる回路が存在するかを問う決定問題である。 C {\displaystyle {\mathcal {C}}} を全ての論理回路の集合とする。この場合の言語 L は次のように定義される。 L = { ⟨ A , k , B , x ⟩ ∈ C × N × C × { 0 , 1 } ∗ | B has at most k gates, and A ( x ) = B ( x ) } {\displaystyle L=\left\{\langle A,k,B,x\rangle \in {\mathcal {C}}\times \mathbb {N} \times {\mathcal {C}}\times \{0,1\}^{*}\left|B{\mbox{ has at most }}k{\mbox{ gates, and }}A(x)=B(x)\right.\right\}} これは多項式時間で決定可能である。次の言語 CM が回路最小化問題を表す言語である。