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:
“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)
“More than a decade after our fellow citizens began bedding down on the sidewalks, their problems continue to seem so intractable that we have begun to do psychologically what government has been incapable of doing programmatically. We bring the numbers down—not by solving the problem, but by deciding it’s their own damn fault.”
—Anna Quindlen (b. 1952)
“Will women find themselves in the same position they have always been? Or do we see liberation as solving the conditions of women in our society?... If we continue to shy away from this problem we will not be able to solve it after independence. But if we can say that our first priority is the emancipation of women, we will become free as members of an oppressed community.”
—Ruth Mompati (b. 1925)