TQBF問題
QBFの式にはたくさんの有用な標準形が存在する。例えば、すべての量化子を式の先頭に移動するような多項式時間多対一帰着が存在することが示せる。さらに別の有用な帰着も存在する。それは各変数の使用とその量化子による束縛の間には高々1つの全称量化子しか存在しないような論理式への帰着であり、IP = PSPACEの証明で用いられた。 QBF formulas have a number of useful canonical forms. For example, it can be shown that there is a polynomial-time many-one reduction that will move all quantifiers to the front of the formula and make them alternate between universal and existential quantifiers. There is another reduction that proved useful in the IP = PSPACE proof where no more than one universal quantifier is placed between each variable's use and the quantifier binding that variable. This was critical in limiting the number of products in certain subexpressions of the arithmetization.