形式陈述

全量化布尔公式真值问题

$$\mathrm{TQBF}=\{⟨\phi ⟩:\phi \text{ 是真的全闭量化布尔公式}\}$$

在多项式时间多一归约下是 PSPACE 完全的。成员关系可按最外层量词递归尝试变量的两个取值，深度优先复用空间，只保存当前赋值路径与公式。困难性把任意多项式空间机器的指数长配置路径写成递归可达谓词，再用一个全称选择位在两段子路径之间共享同一份递归公式，使最终 QBF 的长度保持多项式。

直觉

存在量词表示“计算者选择一个可行分支”，全称量词表示“两个分支都必须成立”。交替量词因此能用多项式长度描述指数大的搜索树，而求值时只需保存当前递归路径。

例子与边界

$\mathrm{\exists }x\mathrm{\forall }y(x\vee y)$ 为真，而 $\mathrm{\forall }x\mathrm{\exists }y(x\wedge y)$ 为假。固定常数量词交替的 QBF 变体位于多项式层级相应层；TQBF 允许交替次数随输入增长，才达到 PSPACE 完全。朴素展开整棵赋值树需要指数时间，但不需要指数空间。

推论与应用

TQBF 是 PSPACE 对应的典型完全问题：规划、博弈和模型检测中的交替选择可归约到它。若 TQBF 有多项式时间算法，则 $\mathrm{P}=\mathrm{PSPACE}$，并使其间所有已知包含类一同坍缩。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§8.3。
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 4。