形式陈述

若对某个 $k\ge 1$ 有

$${\mathrm{\Sigma }}_k^P={\mathrm{\Pi }}_k^P,$$

则

$$\mathrm{PH}={\mathrm{\Sigma }}_k^P.$$

特别地，若 $\mathrm{NP}=\mathrm{coNP}$，则 $\mathrm{PH}=\mathrm{NP}$；若 $\mathrm{P}=\mathrm{NP}$，则 $\mathrm{PH}=\mathrm{P}$。证明对层数归纳：当第 $k$ 层对补封闭时，更高层最外侧相邻的同类量词块可以合并，而相反量词块可借第 $k$ 层的等价表示消去，故新增交替不再增加表达能力。

直觉

多项式层级靠“存在—全称”的新交替逐层增加能力。一旦某层能够在不增加层数的情况下互换最外层量词，后续交替就失去继续抬高层级的支点。

例子与边界

$\mathrm{P}=\mathrm{NP}$ 会使 P 对补封闭的性质传给 NP，从而有 $\mathrm{NP}=\mathrm{coNP}=\mathrm{P}$，再坍缩整个 PH。反向不成立：仅知道 PH 在某个更高层坍缩，不能推出 $\mathrm{P}=\mathrm{NP}$。目前也不知道 PH 是否坍缩。

推论与应用

若某个问题位于 PH 的较高层且能证明它不会导致预期外的层级坍缩，就可排除某些过强的低层算法或归约。坍缩结论因此常被用作条件性困难证据。

参考资料

• Larry J. Stockmeyer, “The Polynomial-Time Hierarchy,” Theoretical Computer Science 3(1), 1976，pp. 1–22。
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 5。