Solving
There is a simple recursive algorithm for determining whether a TQBF is true. Given some QBF
If the formula contains no quantifiers, we can just return the formula. Otherwise, we take off the first quantifier and check both possible values for the first variable:
If, then return . If, then return .
How fast does this algorithm run? For every quantifier in the initial QBF, the algorithm makes two recursive calls on only a linearly smaller subproblem. This gives the algorithm an exponential runtime O(2^n).
How much space does this algorithm use? Within each invocation of the algorithm, it needs to store the intermediate results of computing A and B. Every recursive call takes off one quantifier, so the total recursive depth is linear in the number of quantifiers. Formulas that lack quantifiers can be evaluated in space logarithmic in the number of variables. The initial QBF was fully quantified, so there are at least as many quantifiers as variables. Thus, this algorithm uses O(n + log n) = O(n) space. This makes the TQBF language part of the PSPACE complexity class.
Read more about this topic: True Quantified Boolean Formula
Famous quotes containing the word solving:
“Certainly, young children can begin to practice making letters and numbers and solving problems, but this should be done without workbooks. Young children need to learn initiative, autonomy, industry, and competence before they learn that answers can be right or wrong.”
—David Elkind (20th century)
“Science is a dynamic undertaking directed to lowering the degree of the empiricism involved in solving problems; or, if you prefer, science is a process of fabricating a web of interconnected concepts and conceptual schemes arising from experiments and observations and fruitful of further experiments and observations.”
—James Conant (1893–1978)
“You are right to demand that an artist engage his work consciously, but you confuse two different things: solving the problem and correctly posing the question.”
—Anton Pavlovich Chekhov (1860–1904)