多項式階層
もしそうなら全ての i > k {\displaystyle i>k} について Σ i P = Σ k P {\displaystyle \Sigma _{i}^{\rm {P}}=\Sigma _{k}^{\rm {P}}} となる。特に P = NP なら、階層は完全に潰れる。
多項式階層にある全クラス群の和集合を PH と書く。
多項式時間階層は、指数時間階層や算術的階層に似ている。
PH が PSPACE に包含されることは知られているが、2つのクラスが等しいかどうかは不明である。この問題を言い換えると、PH = PSPACE であるならば、二階述語論理に推移閉包演算子を追加しても強化されないことになる。
もし多項式階層が完全問題を含むなら、どこかの層に潰れる。PSPACE完全問題は存在するので、PSPACE = PH ならば、PSPACE完全問題が Σ k P {\displaystyle \Sigma _{k}^{\rm {P}}} -完全問題だということになるので、多項式階層は潰れる。
多項式階層の各層については ≤ m P {\displaystyle \leq _{\rm {m}}^{\rm {P}}} -完全問題(多項式時間多対一還元において完全な問題)がある。さらに、多項式階層の各層は ≤ m P {\displaystyle \leq _{\rm {m}}^{\rm {P}}} -還元において閉じている。