多项式层级坍缩定理

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

若 $P=NP$，P 对补封闭的性质会传给 NP，从而有 $NP=coNP=P$；存在量词的第一层已能由确定性多项式时间解决，交替量词可逐次消去，故 $PH=P$。更一般地，若对某个 $k$ 有 ${\mathrm{\Sigma }}_k^P={\mathrm{\Pi }}_k^P$，则 $PH={\mathrm{\Sigma }}_k^P$。但本定理没有提供“PH 在某个高层坍缩 $\Rightarrow P=NP$”的推论；这也不是已经证明该蕴涵为假的无条件分离。目前 PH 是否坍缩仍未解决。

只知道某个具体 ${\mathrm{\Sigma }}_k^P$ 完全问题落入较低层，需先确认所用归约及目标类的封闭性才可推出类包含；仅仅属于高层不说明困难性，因为低层问题也属于高层。

条件性困难论证先针对某种算法或归约 $A$ 证明 $A\Rightarrow C$，其中 $C$ 是具体的 PH 坍缩结论；再在“不发生该坍缩”即 $\mathrm{\neg }C$ 的假设下推出 $\mathrm{\neg }A$。例如，若一个关于多项式时间多对一归约的 ${\mathrm{\Sigma }}_2^P$ 完全语言属于 NP，则 ${\mathrm{\Sigma }}_2^P\subseteq NP$。由 $coNP\subseteq {\mathrm{\Sigma }}_2^P$ 得 $coNP\subseteq NP$，取补得到 $NP=coNP$，继而 $PH=NP$。所以在 $PH\ne NP$ 假设下可排除该 NP 算法。真正支撑困难性的是完整性、归约封闭性与非坍缩假设。

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