形式陈述

多项式层级定义为 $\Sigma_0^P=\Pi_0^P=P$${\mathrm{\Sigma }}_0^P={\mathrm{\Pi }}_0^P=P$，$\Sigma_{k+1}^P=NP^{\Sigma_k^P}$${\mathrm{\Sigma }}_{k+1}^P=N{P}^{{\mathrm{\Sigma }}_k^P}$，$\Pi_{k+1}^P=coNP^{\Sigma_k^P}$${\mathrm{\Pi }}_{k+1}^P=coN{P}^{{\mathrm{\Sigma }}_k^P}$，并令 $PH=\bigcup_{k\ge0}\Sigma_k^P$$PH=\bigcup _{k\ge 0}{\mathrm{\Sigma }}_k^P$。等价地，$L\in\Sigma_k^P$$L\in {\mathrm{\Sigma }}_k^P$ 可由多项式时间谓词和至多 $k$$k$ 个交替量词块刻画，首块为存在量词；$\Pi_k^P$${\mathrm{\Pi }}_k^P$ 首块为全称量词。已知 $P\subseteq NP\subseteq PH\subseteq PSPACE$$P\subseteq NP\subseteq PH\subseteq PSPACE$，层级是否严格无限上升未知。

直觉

NP 只有一层“存在证书”；多项式层级交替问“存在一个选择，使得对所有对手选择，又存在回应……”，对应有限轮多项式博弈。

例子与边界

带两层量词的 QSAT 变体 $\exists x\forall y\,\varphi(x,y)$$\mathrm{\exists }x\mathrm{\forall }y\phi (x,y)$ 是典型 $\Sigma_2^P$${\mathrm{\Sigma }}_2^P$ 问题。若 $P=NP$$P=NP$，整个 PH 坍缩到 P；更一般地，若某一层的存在侧与其补侧相等，层级会坍缩到有限层。PH 的定义使用多项式时间预言机查询，而非把预言机内部成本展开。不能宣称 $\Sigma_k^P\subsetneq\Sigma_{k+1}^P$${\mathrm{\Sigma }}_k^P⊊{\mathrm{\Sigma }}_{k+1}^P$ 已被证明；这是核心开放问题。

推论与应用

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，Chs. 1–8。