In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean formula is a formula in quantified propositional logic (also known as Second-order propositional logic) where every variable is quantified (or bound), using either existential or universal quantifiers, at the beginning of the sentence. Such a formula is equivalent to either true or false (since there are no free variables). If such a formula evaluates to true, then that formula is in the language TQBF. It is also known as QSAT (Quantified SAT).
Overview In computational complexity theory, the quantified Boolean formula problem (QBF) is a generalization of the Boolean satisfiability problem in which both existential quantifiers and universal quantifiers can be applied to each variable. Put another way, it asks whether a quantified sentential form over a set of Boolean variables is true or false. For example, the following is an instance of QBF:
∀ x ∃ y ∃ z ( ( x ∨ z ) ∧ y ) {\displaystyle \forall x\ \exists y\ \exists z\ ((x\lor z)\land y)}
QBF is the canonical complete problem for PSPACE, the class of problems solvable by a deterministic or nondeterministic Turing machine in polynomial space and unlimited time. Given the formula in the form of an abstract syntax tree, the problem can be solved easily by a set of mutually recursive procedures which evaluate the formula. Such an algorithm uses space proportional to the height of the tree, which is linear in the worst case, but uses time exponential in the number of quantifiers. Provided that MA ⊊ PSPACE, which is widely believed, QBF cannot be solved, nor can a given solution even be verified, in either deterministic or probabilistic polynomial time (in fact, unlike the satisfiability problem, there's no known way to specify a solution succinctly). It can be solved using an alternating Turing machine in linear time, since AP = PSPACE, where AP is the class of problems alternating machines can solve in polynomial time. When the seminal result IP = PSPACE was shown (see interactive proof system), it was done by exhibiting an interactive proof system that could solve QBF by solving a particular arithmetization of the problem. 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.
Prenex normal form A fully quantified Boolean formula can be assumed to have a very specific form, called prenex normal form. It has two basic parts: a portion containing only quantifiers and a portion containing an unquantified Boolean formula usually denoted as ϕ {\displaystyle \displaystyle \phi } . If there are n {\displaystyle \displaystyle n} Boolean variables, the entire formula can be written as
∃ x 1 ∀ x 2 ∃ x 3 ⋯ Q n x n ϕ ( x 1 , x 2 , x 3 , … , x n ) {\displaystyle \displaystyle \exists x_{1}\forall x_{2}\exists x_{3}\cdots Q_{n}x_{n}\phi (x_{1},x_{2},x_{3},\dots ,x_{n})}
where every variable falls within the scope of some quantifier. By introducing dummy variables, any formula in prenex normal form can be converted into a sentence where existential and universal quantifiers alternate. Using the dummy variable y 1 {\displaystyle \displaystyle y_{1}} ,
∃ x 1 ∃ x 2 ϕ ( x 1 , x 2 ) ↦ ∃ x 1 ∀ y 1 ∃ x 2 ϕ ( x 1 , x 2 ) {\displaystyle \displaystyle \exists x_{1}\exists x_{2}\phi (x_{1},x_{2})\quad \mapsto \quad \exists x_{1}\forall y_{1}\exists x_{2}\phi (x_{1},x_{2})}
The second sentence has the same truth value but follows the restricted syntax. Assuming fully quantified Boolean formulas to be in prenex normal form is a frequent feature of proofs.
QBF solvers
Naive
There is a simple recursive algorithm for determining whether a QBF is in TQBF (i.e. is true). Given some QBF
… excerpt ends here. Continue reading the full article.
