Miscellany
- One important subproblem in TQBF is the Boolean satisfiability problem. In this problem, you wish to know whether a given Boolean formula can be made true with some assignment of variables. This is equivalent to the TQBF using only existential quantifiers:
- This is also an example of the larger result NP PSPACE which follows directly from the observation that a polynomial time verifier for a proof of a language accepted by a NTM (Non-deterministic Turing machine) requires polynomial space to store the proof.
- Any class in the polynomial hierarchy (PH) has TQBF as a hard problem. In other words, for the class comprising all languages L for which there exists a poly-time TM V, a verifier, such that for all input x and some constant i,
- which has a specific QBF formulation that is given as
-
- such that
- where the 's are vectors of Boolean variables.
- It is important to note that while TQBF the language is defined as the collection of true quantified Boolean formulas, the abbreviation TQBF is often used (even in this article) to stand for a totally quantified Boolean formula, often simply called a QBF (quantified Boolean formula, understood as "fully" or "totally" quantified). It is important to distinguish contextually between the two uses of the abbreviation TQBF in reading the literature.
- A TQBF can be thought of as a game played between two players, with alternating moves. Existentially quantified variables are equivalent to the notion that a move is available to a player at a turn. Universally quantified variables mean that the outcome of the game does not depend on what move a player makes at that turn. Also, a TQBF whose first quantifier is existential corresponds to a formula game in which the first player has a winning strategy.
- A TQBF for which the quantified formula is in 2-CNF may be solved in linear time, by an algorithm involving strong connectivity analysis of its implication graph. The 2-satisfiability problem is a special case of TQBF for these formulas, in which every quantifier is existential.
- There is a systematic treatment of restricted versions of quantified boolean formulas (giving Schaefer-type classifications) provided in an expository paper by Hubie Chen.
Read more about this topic: True Quantified Boolean Formula
Famous quotes containing the word miscellany:
“The secret of culture is to learn, that a few great points steadily reappear, alike in the poverty of the obscurest farm, and in the miscellany of metropolitan life, and that these few are alone to be regarded,—the escape from all false ties; courage to be what we are; and love what is simple and beautiful; independence and cheerful relation, these are the essentials,—these, and the wish to serve,—to add somewhat to the well-being of men.”
—Ralph Waldo Emerson (1803–1882)
“Happy will that house be in which the relations are formed from character; after the highest, and not after the lowest order; the house in which character marries, and not confusion and a miscellany of unavowable motives.”
—Ralph Waldo Emerson (1803–1882)