TQBF問題
計算複雑性理論において、量化されたブール式問題(QBF)は充足可能性問題の一般化であり、変数を存在量化子でも全称量化子でも量化することができる。言い換えると、QBFはブール変数の集合の上の量化された式が真か偽かを問うものである。例えば、以下の式はQBFのインスタンスである:
∀ x ∃ y ∃ z ( ( x ∨ z ) ∧ y ) {\displaystyle \forall x\ \exists y\ \exists z\ ((x\lor z)\land y)}
QBFは標準的なPSPACE完全問題である。PSPACEは決定性、あるいは非決定性チューリングマシンで多項式領域および無制限の時間で解ける問題のクラスである。 式を抽象構文木の形で与えれば、この問題は式を評価するような再帰的な手続きによって簡単に解くことができる。このアルゴリズムの領域計算量は木の高さに比例し、最悪ケースでは線型であるが、時間計算量は量化子の個数に関する指数である。
広く信じられている MA ⊊ PSPACEという仮定の下で、QBFは決定性チューリングマシンでも確率的チューリングマシンでも、多項式時間では解くことも与えられた解を検証することもできない。実際、充足可能性問題とは異なり、解を簡潔に指定する方法は知られていない。交代チューリングマシンを使えば線型時間で自明に解けるが、AP = PSPACEなのでこれは当然である(APは交代チューリングマシンで多項式時間で解ける問題の集合)。
独創的な結果IP = PSPACE(参考:対話型証明系)が示されたとき、その証明はQBFを解くことのできる対話型証明系を示すことで行われた。