多项式层级（Polynomial Hierarchy）

多项式层级（Polynomial Hierarchy，简称PH）是计算复杂度理论中的一个类层次结构，它将NP和co-NP按存在量词与全称量词的交替次数逐级推广，形成一座由无穷多层构成的复杂度金字塔。

概述

层级的最底层是P。其上按量词交替定义：第一层的存在部分是NP，全称部分是co-NP；更高层通过在前一层复杂度类上附加神谕，或等价地增加一次量词交替来构造。整个多项式层级PH是所有层的并集。

核心特点

• 逐层定义：Σ层以存在量词起头，Π层以全称量词起头，Δ层用前一层作神谕。
• 量词交替：第k层对应量化布尔公式中k次量词块交替，难度随层数上升。
• 包含关系：P包含于PH，PH整体又包含于PSPACE。
• 塌缩性质：若某两层相等，则整个层级塌缩到该层为止。

核心原理

多项式层级可用两种等价方式刻画：一是神谕视角，高层类由低层类作为神谕加以定义；二是逻辑视角，用带有限次量词交替的谓词表达，恰对应量化布尔公式的受限片段。学界普遍猜想该层级不塌缩，即每一层都严格大于下一层。若P等于NP，或NP等于co-NP，都会导致层级立即塌缩到较低层，因此层级是否无穷是刻画这些开放问题的重要框架。

应用场景

多项式层级用于精确定位那些看似比NP更难、却仍在多项式空间内的问题，例如最短公式判定、某些博弈与优化问题的最优性验证、电路最小化等，为它们标注恰当的难度层级提供了统一坐标。

常见问题

问：多项式层级和PSPACE是什么关系？答：整个PH都包含于PSPACE；但一般猜想PH严格小于PSPACE，因为PSPACE允许多项式次量词交替，而PH每个问题只用常数次。

问：为什么说层级会塌缩？答：若某一层等于其上一层，可证明所有更高层都与之相等，整座金字塔便坍缩为有限层，这被视为不太可能发生的情形。