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

Since each of r , s , t ,and u can be expressed as a conjunction of q terms of t h e form
( x j = y j ) and ( x j = y j )=( x j y j ∨ q , it follows that r , s , t ,and u

c a n e a ch be expressed as a disjunction of 2 q terms. Each of the four terms of t he form
( r

x j y j ) ,1 ≤ i ≤

t ) consists of 4 q 2 terms, each of which is a conjunction of four literals. Thus, g is the
disjunction of 16 q 2 termsoffourliteralseach.
Given the regular structure of this formula for ψ i , it can be generated from a formula for
ψ i− 1 in space O (log q ) .Since0

∧

k and k is polynomial in the length of the input, all
the formulas, including that for ψ k , can be generated in log-space. By the above reasoning,
this formula is a “Yes” instance of QUANTIFIED UNSATISFIABILITY if and only if there is a
path in the configuration graph G ( M , w ) between the initial and final states.

≤ i ≤

Combining the two results, we have the following theorem.

THEOREM 8.12.1 QUANTIFIED SATISFIABILITY is log-space complete for PSPACE .

8.12.2 Other PSPACE -Complete Problems
An important version of QUANTIFIED SATISFIABILITY is ALTERNATING QUANTIFIED SAT -
ISFIABILITY .

ALTERNATING QUANTIFIED SATISFIABILITY
Instance: Instances of QUANTIFIED SATISFIABILITY that have an even number of quanti-
fiers that alternate between the first quantifier.

Answer: “Yes” if the instance is a “Yes” instance of QUANTIFIED SATISFIABILITY .

∃ and ∀ ,with ∃

THEOREM 8.12.2 ALTERNATING QUANTIFIED SATISFIABILITY islog-spacecompletefor
PSPACE .
Proof ALTERNATING QUANTIFIED SATISFIABILITY is in PSPACE because it is a special
case of QUANTIFIED SATISFIABILITY .Wereduce QUANTIFIED SATISFIABILITY to AL -
TERNATING QUANTIFIED SATISFIABILITY in log-space as follows. If two universal quan-
tifiers appear in succession, we add an existential quantifier between them in a new variable,
say x l , and add the new clause at the end of the formula φ . If two existential quan-

tifiers appear in succession, add universal quantification over a new variable and a clause
containing it and its negation. If the number of quantifiers is not even, repeat one or the
other of the above steps. This transformation at most doubles the number of variables and
clauses and can be done in log-space. The instance of ALTERNATING QUANTIFIED SATIS -
FIABILITY is a “Yes” instance if and only if the instance of QUANTIFIED SATISFIABILITY is
a“Yes”instance.

{ x l , x l }

The new version of QUANTIFIED SATISFIABILITY is akin to a game in which universal
and existential players alternate. The universal player attempts to show a fact for all values of
its Boolean variable, whereas the existential player attempts to deny that fact by the choice of
its existential variable. It is not surprising, therefore, that many games are PSPACE -complete.
The geography game described below is of this type.
The geography game is a game for two players. They alternate choosing names of cities
in which the first letter of the next city is the last letter of the previous city until one of the two
players (the losing player) cannot find a name that has not already been used. (See Fig. 8.18 .)
This game is modeled by a graph in which each vertex carries the name of a city and there is