多項式階層
つまり、この階層上のあるクラス C {\displaystyle {\mathcal {C}}} と言語 L ∈ C {\displaystyle L\in {\mathcal {C}}} があるとき、 A ≤ m P L {\displaystyle A\leq _{\rm {m}}^{\rm {P}}L} ならば、同時に A ∈ C {\displaystyle A\in {\mathcal {C}}} である。これらの事実から、 K i {\displaystyle K_{i}} を Σ i P {\displaystyle \Sigma _{i}^{\rm {P}}} の完全問題としたとき、 Σ i + 1 P = ( Σ i P ) K i {\displaystyle \Sigma _{i+1}^{\rm {P}}=\left(\Sigma _{i}^{\rm {P}}\right)^{K_{i}}} と Π i + 1 P = ( Π i P ) K i c {\displaystyle \Pi _{i+1}^{\rm {P}}=\left(\Pi _{i}^{\rm {P}}\right)^{K_{i}^{\rm {c}}}} が成り立つことがわかる。実際、 Σ 2 P = N P S A T {\displaystyle \Sigma _{2}^{\rm {P}}={\rm {NP}}^{\rm {SAT}}} である。言い換えれば、言語を C {\displaystyle {\mathcal {C}}} に含まれる何らかの神託機械に基づいて定義したとき、それを C {\displaystyle {\mathcal {C}}} の完全問題に基づいて定義したと見なすことができる。完全問題は従って、それが完全であるとするクラスを代表していると見なせる。