(V:r)((3y)((Vz)(F)))

with only the one pair of parentheses around F, rather than one pair for each quantifier on the chain, i.e., as (Vj;)(3j/)(Vz)(F).

Example 11.7: Here is an example of a QBF:

iVx){i3y){xy) + 0/z)bx + z)) (11.1)

Starting with the variables x and y, we connect them with AND and then apply the quantifier (3y) to make the subexpression {By){xy). Similarly, we construct the boolean expression -ix + z and apply the quantifier (Vz) to make the subexpression {\/z)(->x + z). Then, we combine these two expressions with an OR; no parentheses are necessary, because + (OR) has lowest precedence. Finally, we apply the (Var) quantifier to this expression to produce the QBF stated. □

11.3,3 Evaluating Quantified Boolean Formulas

We have yet to define formally what the meaning of a QBF is. However, if we read V as for all and 3 as exists, we can get the intuitive idea. The QBF asserts that for all x (i.e., x - Q m x - 1), either there exists у such that both X and у are true, or for all z, ->x + z is true. This statement happens to be true. To see why, note that if x - 1, then we can pick у = \ and make xy true, if X = 0, then -x -\- z is true for both values of z.

If a variable x is in the scope of some quantifier of x, then that use of x is said to be bound. Otherwise, an occurrence of x is free.

formulas are defined as foUows:

1. 0 (false) ; 1 (true), and any variable are QBFs.

2. If £ and F are QBFs then so are (E), ->{Е), (E) A (F), and (E) V (F), representing a parenthesized E, the negation of E, the AND of E and F, and the OR of E and F. respectively. Paientheses may be removed if they are redundant, using the usual precedence rules: NOT, then AND, then OR (lowest). We shall also tend to use the arithmetic style of representing AND and OR, where AND is represented by juxtaposition (no operator) and OR is represented by +, That is, we often use {Е){Е) in place of (E) A [F) and use (E) + (F) in place of (E) V (E).

3. If F is a QBF that does not include a quantification of the variable ж, then (Va;)(E) and (3a:)(F) are QBFs. We say that the scope of x is the expression E. Intuitively, x is only defined within F, much as the scope of a variable in a program has a scope that is the function in which it is declared. Parentheses around F (but not around the quantification) can be removed if there is no ambiguity. However, to avoid an excess of nested parentheses, we shall write a chain of quantifiers such as

Example 11.8: Each use of a variable in the QBF of Equation (11.1) is bound, because it is in the scope of the quantifier for that variable. For instance, the scope of the variable y, quantified in {3y){xy), is the expression xy. Thus, the occurrence of у there is bound. The use of x in xy is bound to the quantifier (Vi) whose scope is the entire expression. □

The value of a QBF that has no free variables is either 0 or 1 (i.e., false or true, respectively). We can compute the value of such a QBF by induction on the length n of the expression.

BASIS: If the expression is of length 1, it can only be a constant 0 or 1, because any variable would be free. The value of that expression is itself.

INDUCTION: Suppose we are given an expression with no free variables and length n > 1, and we can evaluate any expression of shorter length, as long as that expression has no firee variables. There are six possible forms such a QBF can have:

1. The expression is of the form (E). Then E is of length n-2 and can be evaluated to be either 0 or 1. The value of (E) is the same.

2. The expression is of the form -E. Then E is of length n -1 and can be evaluated. If £ - 1, then -lE - 0, and vice versa.

3. The expression is of the form EF. Then both E and F are shorter than n, and so can be evaluated. The value of EF is 1 if both E and F have the value 1, and EF = 0 if either is 0.

4. The expression is of the form E + F. Then both E and F are shorter than n, and so can be evaluated. The value oi E + F is 1 if either E or F has the value 1, and £; + = 0 if both are 0.

5. If the expression is of the form {Vx){E), first replace all occurrences of x in S by 0 to get the expression Eo, and also replace each occurrence of x in E by 1, to get the expression E. Observe that Eo and Ei both:

(a) Have no free variables, because any occurrence of a firee variable in Eq or El could not be x, and therefore would be some variable that is also free in E.

(b) Have length n - 6, and thus are shorter than n.

Evaluate Eo and Ei. If both have value 1, then (Vx)(£) has value 1; otherwise it has the value 0. Note how this rule reflects the for all x interpretation of (Vi).

6. If the given expression is {Bx){E), then proceed as in (5), constructing Eo and El, and evaluating them. If either Eo or Ei has value 1, then (Bx){E) has value 1; otherwise it has value 0. Note that this rule reflects the exists interpretation of (Зх).

Notice our use of alternative notations for AND and OR, since we cannot use juxtaposition and + for expr(?ssion3 involving Os and 1з without making the expressions loolt either lilte multidigit numbers or adthmetic addition. We hope the reader can accept both notations as standing for tlie same logical operators.

Example 11.9: Let us evaluate the QBF of Equation (11.1). It is of the form (Va;)(E), so we must first evaluate Eq, which is:

i3y)iOy} + ibO + z) (11.2)

The value of this expression depends on the values of the two expressions connected by the OR: (3y)(0j/) and (V)(-.0 + z); Eq has value 1 if either of those expressions does. To evaluate (Зу) (Oy), we must substitute у = 0 and у = 1 in subexpression Oy, and check that at least one of them has the value 1. However, both 0 Л 0 and 0 Л 1 have the value 0, so {3у)[0у) has value 0.

Fortunately, {Vz){->0 + z) has value 1, as we can see by substituting both z = 0 and г - 1. Since -lO = 1, the two expressions we must evaluate are 1 V 0 and 1 V 1. Since both have value 1, we know that (V2:)(-iO + z) has value 1. We now conclude that Eo, which is Equation (11.2), has value 1.

We must also check that Ey, which we get by substituting a; = 1 in Equation (11.1);

{3y)ily) + iyz)i-,l + z) (11.3)

also has value 1. Expression {3y){ly) has value 1, as we can see by substituting у = 1. Thus, El, Equation (11.3), has value 1. We conclude that the entire expression. Equation (11.1), has value 1. □

11.3.4 PS-Completeness of the QBF Problem

We can now define the quantified boolean formula problem: Given a QBF with no free variables, does it have the value 1? We shall refer to this problem as QBF, while continuing also to use QBF as an abbreviation for quantified boolean formula. The context should allow us to avoid confusion.

We shall show that the QBF problem is complete for VS. The proof combines ideas from Theorems 10.9 and 11.5. Prom Theorem 10.9, we use the idea of representing a computation of a TM by logical variables each of which teUs whether a certaui cell has a certain value at a certain time. However, when we were dealing with polynomial time, as we were in Theorem 10.9, there were only polynomially many variables to concern us. We were thus able to generate, in polynomial time, ал expression saying that the TM accepted its input. When we deal with a polynomial space bound, the number of IDs in the computation can be exponential in the input size, so we cannot, in polynomial time, write a boolean expression to say that the computation is correct. Fortunately, we are given a more powerful language to express what we need to say, and the availability of quantifiers lets us write a polynomial-length QBF that says the polynomial-space-bounded TM accepts its input.