True quantified Boolean formula

In complexity theory, the satisfiability problem for quantified Boolean formulas ( QBF, or often only briefly QSAT ) is a generalization of the satisfiability problem of propositional logic. It examines whether a provided with quantifiers propositional formula is satisfiable or true. It is the canonical PSPACE - complete problem.

If the satisfiability of boolean formulas without free variables considered, satisfiability is equivalent to truth. The resulting problem True Quantified Boolean Formula, short TQBF is also PSPACE -complete.

  • 2.1 Quantorenwechsel and Polynomialzeithierarchie

Quantified Boolean formulas

Every propositional formula can be expanded by adding universal and existential quantifiers. The semantics of a formula so formed is similar to the semantics of predicate logic formulas.

Syntax

The amount of quantified Boolean formulas can be defined inductively as follows:

  • Each propositional variable is a quantified Boolean formula. occur free in the formula
  • Are and quantified boolean formulas, including and. A propositional variable, or is free in the formulas, if is in or free.
  • Is a quantified boolean formula and a propositional variable, so are and quantified boolean formulas. The scope of or relate to each free occurrence of in. Any other non-bound propositional variable is free in and.

Semantics

The semantics of quantified Boolean formulas is closely aligned with the semantics of predicate logic: The value of a quantified Boolean formula of the form is determined by replacing by, where and arise because each occurrence of is replaced by 0 or 1. Similarly, each volume of through is replaced.

A formula that contains no free variables, so that is either true or false.

Prenex normal form

A quantified boolean formula is in prenex normal form if it is of the form, where and are variables of a propositional formula without quantifiers are. The term is called Quantorenblock.

Since for every quantified Boolean formula, an equivalent formula in prenex normal form exists and it can be constructed in polynomial time, is often assumed in proofs of this form.

The satisfiability

The satisfiability problem for quantified boolean formulas is to decide whether a given quantified boolean formula is true or false without free variables.

From the definition of the semantics for quantified boolean formulas, a simple recursive algorithm can be derived, which solves the satisfiability problem for quantified Boolean formulas in prenex normal form: When entering a formula of the form

For a propositional formula and quantifiers, the value of calculated if no quantifiers are present. Otherwise, the value is calculated from and in case the value of the case.

In a quantified boolean formula with quantifiers so the algorithm requires steps. However, the space required is quadratic in the length of the formula, the problem is thus PSPACE. Furthermore it could be shown that the decision problem is PSPACE - hard. This problem is now complete for the class PSPACE.

Quantorenwechsel and Polynomialzeithierarchie

From the structure of the Quantorenblocks a quantified boolean formula in prefix normal form, conclusions can be drawn regarding complexity-theoretic properties. The classes of true quantified boolean formulas in prefix normal form depending on the number of alternations of universal and existential quantifiers and their order completely for one stage of Polynomialzeithierarchie. Following is the notation for for any number of a quantifier.

If the class of all true quantified boolean formulas without free variables of the form

And the class of all true quantified boolean formulas without free variables of the form

So applies to all:

  • , is completely and
  • Is -complete.

References and sources

  • Mathematical Logic
  • Complexity Theory
311693
de