QBF
quantified boulean formula
$ \text{QBF} := \{\psi | \psi = (Q_1 x_1)...(Q_n x_n)\phi(x_1,...,x_n), Q_i \in \{\forall, \exists\}, \phi \in \text{CNF}\}
ノーテーション
$ \left[(Q_{n+1} x_{n+1})(Q_n x_n)...(Q_0 x_0)\phi(x_0,...,x_n,x_{n+1}) \right][b] := (Q_n x_n)...(Q_n x_0)\phi(x_0,...,x_n, b) とする