多项式层级

NP 只有一层“存在证书”，PH 则反复交替“存在一个短证书”和“对所有短挑战，又存在回应……”，形成有限轮多项式博弈和多项式时间谓词的有限量词层级。${\mathrm{\Sigma }}_k^P$ 从存在量词开始，${\mathrm{\Pi }}_k^P$ 从全称量词开始；固定 $k$ 时量词块数量不随输入增长。它也可用带上一层预言机的 NP/coNP 递归定义，这两种视角分别突出逻辑结构和算法访问。

带两层量词的 QSAT 变体 $\mathrm{\exists }x\mathrm{\forall }y\phi (x,y)$ 是典型 ${\mathrm{\Sigma }}_2^P$ 问题。若 $P=NP$，整个 PH 坍缩到 P；更一般地，

PH 的定义使用多项式时间预言机查询，而非把预言机内部成本展开。不能宣称 ${\mathrm{\Sigma }}_k^P⊊{\mathrm{\Sigma }}_{k+1}^P$ 已被证明；这是核心开放问题。

形如

且 $R$ 可多项式时间判定的语言属于 ${\mathrm{\Sigma }}_3^P$。SAT 位于 ${\mathrm{\Sigma }}_1^P=NP$，TAUT 位于 ${\mathrm{\Pi }}_1^P=coNP$；带一次 NP 预言机的 NP 机器刻画 ${\mathrm{\Sigma }}_2^P$。

PH 只允许常数层交替；若交替次数可随输入多项式增长，能力上升到 PSPACE。把所有层的并集理解成“存在某个固定 $k$”而非单一算法可动态选择任意层数。

这里的 oracle 查询是向完整语言发出的多项式时间成员查询。它不同于读取隐藏输入坐标的位查询公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。、返回近似期望的统计查询，也不同于只承诺 gap decision 的性质测试公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。。通信复杂度不按量词层数收费，而按参与者交换的消息收费；只有在给定 gadget 和模拟定理后，lifting公理库通信复杂度 lifting 定理Communication complexity lifting theorem · Query-to-communication lifting用两方 gadget 替换外层函数的每个输入位，把查询树下界提升为组合通信函数及其相关模型下界。才可能把查询下界搬到通信或电路场景。把“有 oracle”或“有交替”当作这些亚线性模型的直接上界，会漏掉输入分割、访问接口与误差量词。

PH 为优化解的唯一性、最小性、可验证稳健性等带有限量词交替的问题提供精确位置，也用于描述复杂性坍缩后果和归约边界。

NP公理库复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。 与 coNP公理库复杂度类 coNPComplexity class co-NP · coNP补语言属于 NP 的语言类。 构成第一层，预言机图灵机公理库预言机图灵机Oracle Turing machine可在一步内查询某固定语言成员资格的相对可计算性模型。 给出递归定义。坍缩定理公理库多项式层级坍缩定理Polynomial hierarchy collapse theorem · PH collapse若多项式层级某层的存在侧与全称侧相等，则整个层级坍缩到该层。 说明层间等式的后果，Sipser–Gács–Lautemann 与 Toda 定理则把随机性和计数复杂度放到这一层级周围。