4.1 多项式层级（Polynomial Hierarchy, PH）

文档摘要

4.1 多项式层级（Polynomial Hierarchy, PH） 4.1 多项式层级（Polynomial Hierarchy, PH）在计算复杂性理论的宏大画卷中，多项式层级（Polynomial Hierarchy, PH）犹如一座精密的阶梯金字塔，矗立于P与NP的永恒谜题之上。它不仅承接了前述章节对P、NP及$\Sigma1^P$（即NP）的奠基性探讨，更为后续章节中PSPACE、EXPTIME等更高复杂性类铺设了坚实的理论桥梁。试想，如果NP问题只是单层“存在性”量化，那PH又如何层层叠加“全称-存在”交替，铸就出一座无限延伸却又可能坍塌的复杂性堡垒？本节将深入剖析PH的核心架构，从其定义与层级构造入手，逐步揭示算术层级的多项式模拟机制，以及归约折叠下潜在的崩溃边界。