NP
このとき、 NP = Σ 1 P {\displaystyle {\textsf {NP}}=\Sigma _{1}^{\rm {P}}} 、 co-NP = Π 1 P {\displaystyle {\textsf {co-NP}}=\Pi _{1}^{\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 層で潰れる」と言うが、
もし P = NP {\displaystyle {\textsf {P}}={\textsf {NP}}} なら、階層は完全に潰れ、 NP = co-NP = PH {\displaystyle {\textsf {NP}}={\textsf {co-NP}}={\textsf {PH}}} 。
もし NP = co-NP {\displaystyle {\textsf {NP}}={\textsf {co-NP}}} なら、階層が第1層で潰れ、 NP = PH {\displaystyle {\textsf {NP}}={\textsf {PH}}} 。
つまりP≠NP予想は、多項式階層で考えると「完全には潰れない」という予想に換言できる。多項式階層は、すべての階層で潰れないと考えられているが、未解決問題である。