Complexity Classes - Models of Computation: Exploring the Power of Computing - page 367

tree eval( n , φ , Q , d , w ) ;
if d = n then
return(evaluate( φ , w )) ;
else
if first ( Q )=

∃

then
return(tree eval( n , φ , rest( Q ), d + 1, w 0 )
OR tree eval( n , φ , rest( Q ), d + 1, w 1 )) ;

else
return(tree eval( n , φ , rest( Q ), d + 1, w 0 )
AND tree eval( n , φ , rest( Q ), d + 1, w 1 )) ;

Figure 8.17 A program for the recursive procedure tree eval ( n , φ , Q , d , w ). The tuple w

keeps track of the path taken into the tree.

The circuit C qsat has size exponential in n because there are 2 n values for the n variables.
However, it can be evaluated in polynomial space, as we show. For this purpose consider the
recursive procedure tree eval( n , φ , Q , d , w ) in Fig. 8.17 that evaluates C qsat .Here n is
the number of variables in the quantization, d is the depth of recursion, φ is the expression
over which quantification is done, Q is a sequence of quantifiers, and w holds the values for
d variables. Also, first( Q ) and rest( Q ) are the first and all but the first components of
Q , respectively. When d = 0, Q =( Q 1 , Q 2 , ... , Q n ) and Q 1 x 1 Q 2 x 2 Q n x n φ is the

expression to evaluate. We show that tree eval( n , φ , Q ,0, ) can be computed in space
quadratic in the length of an instance of QUANTIFIED SATISFIABILITY .
When d = n , the procedure has reached a leaf of the tree and the string w contains
values for the variables x 1 , x 2 , ... , x n , in that order. Since all variables of φ are known when
d = n , φ can be evaluated. Let evaluate ( φ , w ) be the function that evaluates φ with values
specified by w . Clearly tree eval( n , φ , Q ,0, ) is the value of Q 1 x 1 Q 2 x 2 ···

···

Q n x n φ .
We now determine the work space needed to compute tree eval( n , φ , Q , d , w ) on
a DTM. (The discussion in the proof of Theorem 8.5.5 is relevant.) Evaluation of this
procedure amounts to a depth-first traversal of the tree. An activation record is created for
each call to the procedure and is pushed onto a stack. Since the depth of the tree is n ,atmost
n + 1 records will be on the stack. Since each activation record contains a string of length at
most O ( n ) , the total space used is O ( n 2 ) .Andthelengthof Q 1 x 1 Q 2 x 2 ···

Q n x n φ is at

least n , the space is polynomial in the length of this formula.

LEMMA 8.12.2 QUANTIFIED SATISFIABILITY is log-space hard for PSPACE .
Proof Our goal is to show that every decision problem PSPACE can be reduced in

log-space to an instance of QUANTIFIED SATISFIABILITY . Instead, we show that every such
P

P∈

can be reduced in log-space to a “No” instance of QUANTIFIED SATISFIABILITY (we call
this QUANTIFIED UNSATISFIABILITY ). But a “No” instance is one for which the formula
φ , which is in product-of-sums form, is not satisfied under the specified quantification or
that its Boolean complement, which is in sum-of-products expansion (SOPE) form, is sat-
isfied under a quantification in which

and vice versa. Exchanging “Yes”
and “No” instances of decision problems (which we can do since PSPACE is closed un-

∀ is replaced by ∃