多项式层级坍缩定理

多项式层级靠“存在—全称”的量词块交替逐层增加表达力；坍缩定理说明，一旦某个较低层能在不增加层数的情况下模拟它的对偶或下一层，后续交替就失去继续抬高层级的支点，不再产生新类。证明通常把更高层公式中的相邻量词块吸收到已坍缩层，并逐层归纳。它是条件性结构结论：假设发生某个等式才推出整个层级收缩，并没有无条件证明层级真的坍缩。

若 $P=NP$，P 对补封闭的性质会传给 NP，从而有 $NP=coNP=P$；存在量词的第一层已能由确定性多项式时间解决，交替量词可逐次消去，故 $PH=P$。更一般地，若对某个 $k$ 有 ${\mathrm{\Sigma }}_k^P={\mathrm{\Pi }}_k^P$，则 $PH={\mathrm{\Sigma }}_k^P$。反向不成立：仅知道 PH 在某个更高层坍缩，不能推出 $P=NP$；目前也不知道 PH 是否坍缩。

只知道某个具体 ${\mathrm{\Sigma }}_k^P$ 完全问题落入较低层，需先确认归约封闭性才可推出类包含。结论方向不能倒置：$PH$ 坍缩到某层并不自动给出 $P=NP$，除非坍缩层就是 P。

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

它依赖 多项式层级公理库多项式层级Polynomial hierarchy · PH由交替存在和全称多项式证书或逐层 NP 预言机构成的复杂性层级。 的交替量词结构，并把 P公理库复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。、NP公理库复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。 与 coNP公理库复杂度类 coNPComplexity class co-NP · coNP补语言属于 NP 的语言类。 的潜在等式放大为全局后果。电路下界、稀疏完全集和随机复杂度包含常通过“否则 PH 坍缩”给出条件性不可能结果。