多項式階層
定義から、次のような関係が成り立つ。
Σ i P ⊆ Δ i + 1 P ⊆ Σ i + 1 P {\displaystyle \Sigma _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Sigma _{i+1}^{\rm {P}}} Π i P ⊆ Δ i + 1 P ⊆ Π i + 1 P {\displaystyle \Pi _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Pi _{i+1}^{\rm {P}}} Σ i P = c o Π i P {\displaystyle \Sigma _{i}^{\rm {P}}={\rm {co}}\Pi _{i}^{\rm {P}}}
真の包含であることがわかっている算術的階層や解析的階層とは異なり、これらの包含関係が厳密かどうか(真部分集合かどうか)は未解決の問題である。ただし、これら全てが厳密な包含関係であると広く信じられている。もしこれが成り立たず、ある k について Σ k P = Σ k + 1 P {\displaystyle \Sigma _{k}^{\rm {P}}=\Sigma _{k+1}^{\rm {P}}} すなわち Σ k P = Π k P {\displaystyle \Sigma _{k}^{\rm {P}}=\Pi _{k}^{\rm {P}}} となることを「多項式階層が第 k 層で潰れる」と言う。