计算复杂性理论中的多项式谱系 我们先从计算复杂性理论的基础开始。计算复杂性理论研究计算问题所需的资源（如时间、空间）下界，并将问题按难度分类。您已熟悉P与NP问题：P类包含在多项式时间内可被确定性图灵机判定的问题，而NP类包含在多项式时间内可被非确定性图灵机判定的问题，且其解可被确定性验证。多项式谱系（Polynomial Hierarchy, PH）是NP和co-NP类的推广，它通过交替量词定义了一个层次结构，用于分类更高复杂度的计算问题。 接下来，我们定义多项式谱系。多项式谱系由一系列复杂性类Σₖᴾ、Πₖᴾ和Δₖᴾ组成，其中k是自然数（k ≥ 0）。这些类通过交替使用存在和全称量词在多项式时间内定义。基础层（k=0）为Σ₀ᴾ = Π₀ᴾ = P，Δ₀ᴾ = P。对于k ≥ 1，类定义如下： Σₖᴾ：由存在量词后跟一个Πₖ₋₁ᴾ谓词定义，即问题形式为∃y. R(x,y)，其中R是Πₖ₋₁ᴾ中的谓词，且|y|是|x|的多项式大小。 Πₖᴾ：由全称量词后跟一个Σₖ₋₁ᴾ谓词定义，即问题形式为∀y. R(x,y)，其中R是Σₖ₋₁ᴾ中的谓词。 Δₖᴾ：在Σₖᴾ类中可被确定性图灵机在多项式时间内解决的问题，等价于P^Σₖ₋₁ᴾ（即带有Σₖ₋₁ᴾ预言机的多项式时间）。 多项式谱系是所有类的并集：PH = ∪ₖ Σₖᴾ。 然后，我们探讨多项式谱系的性质。多项式谱系具有层次结构：Σₖᴾ ⊆ Σₖ₊₁ᴾ 且 Πₖᴾ ⊆ Πₖ₊₁ᴾ，且如果某一层坍缩（例如Σₖᴾ = Πₖᴾ），则整个谱系坍缩到该层，即PH = Σₖᴾ。这称为谱系坍缩。例如，如果P = NP，则PH = P。谱系中的问题示例包括：Σ₁ᴾ = NP（如SAT问题），Π₁ᴾ = co-NP（如TAUTOLOGY），Σ₂ᴾ包含如“存在一个赋值使得所有电路输出满足某条件”的问题。多项式谱系与预言机相关：例如，有预言机使得PH无限，但也有证据表明PH可能严格分层。 最后，我们讨论多项式谱系的意义和开放问题。多项式谱系提供了对NP以上问题复杂度的分类工具，在密码学、证明理论和自动推理中有用。例如，量化布尔公式（QBF）问题在PH中，且如果PH不坍缩，则QBF不在较低层。主要开放问题包括PH是否严格分层（即每层都不同），以及PH是否等于PSPACE（多项式空间）。这些问题的解决将深化我们对计算本质的理解。