4.1.2 归约与折叠：PH 崩溃的可能性

文档摘要

4.1.2 归约与折叠：PH 崩溃的可能性 4.1.2 归约与折叠：PH 崩溃的可能性想象一下，你正站在计算复杂性理论的悬崖边上，多项式层级（Polynomial Hierarchy, PH）如同一座层层叠加的摩天大楼，每一层都代表着更复杂的存在量词嵌套。如果某层突然与下方层级“折叠”在一起，整个大楼就会轰然坍塌到某个固定高度。这不是科幻，而是PH崩溃的核心谜题：通过精心设计的归约，我们能否证明或模拟这种坍塌？作为一名深耕复杂性理论的工程师，我曾在SAT求解器和QBF（Quantified Boolean Formulas）验证器上亲手实现过这些归约。