TQBF 问题

给布尔表达式加上存在量词和全称量词可以将其变为量化的表达式。如果所有的变量都对应一个量词，则称该表达式是完全量化的，也是一个语句，具有确定的真值。

这样的语句可以写成 prenex 范式，即将所有的量词写在表达式前面。

定义语言

$$T Q B F=\{\langle\phi\rangle \mid \phi \text { is a true fully quantified Boolean formula }\} .$$

它是 PSPACE 完全复杂度类的。

TQBF 问题和公式游戏问题等价。