Information Technology Reference
In-Depth Information
In this section we establish the following result, stronger than PSPACE -completeness of
QUANTIFIED SATISFIABILITY :weshowitiscompletefor PSPACE under log-space trans-
formations. Reductions of this type are potentially stronger than polynomial-time reductions
because the transformation is executed in logarithmic space, not polynomial time. While it
is true that every log-space transformation is a polynomial-time transformation (see Theo-
rem 8.5.8 ), it is not known if the reverse is true. We prove this result in two stages: we first
show that QUANTIFIED SATISFIABILITY is in PSPACE and then that it is hard for PSPACE .
LEMMA 8.12.1 QUANTIFIED SATISFIABILITY is in PSPACE .
Proof To s h ow t h a t QUANTIFIED SATISFIABILITY is in PSPACE we evaluate in polyno-
mial space a circuit, C qsat , whose value is 1 if and only if the instance of QUANTIFIED
SATISFIABILITY is a “Yes” instance. The circuit C qsat is a tree all of whose paths from the
inputs to the output (root of the tree) have the same length, each vertex is either an AND
gate or an OR gate, and each input has value 0 or 1. (See Fig. 8.16 .) The gate at the root of
the tree is associated with the variable x 1 , the gates at the next level are associated with x 2 ,
etc. The type of gate at the j th level is determined by the j th quantifier Q j and is AND if
Q j =
. The leaves correspond to all 2 n the values of the n variables:
at each level of the tree the left and right branches correspond to the values 0 and 1 for the
corresponding quantified variable. Each leaf of the tree contains the value of the formula φ
for the values of the variables leading to that leaf. In the example of Fig. 8.16 the left m ost
le a f has value 1 be ca u se o n input x 1 = x 2 = x 3 = 0 each of the three clauses
and OR if Q j =
{
x 1 , x 2 , x 3
}
,
{
is satisfied.
It is straightforward to see that the value at the root of the tree is 1 if all clauses are
satisfied under the quantifiers Q 1 x 1 Q 2 x 2
x 1 , x 2 , x 3
}
and
{
x 1 , x 2 , x 3
}
Q n x n and 0 otherwise. Thus, the circuit solves
the QUANTIFIED SATISFIABILITY problem and its complement. (Note that PSPACE =
coPSPACE , as shown in Theorem 8.6.1 .)
···
0
x 1
0
1
1
0
x 2
01
0
1
0
0
x 3
01
1
0
1
1
0
1
1
0
Fi gure 8 .16 A tree circ ui t co n stru ct ed from the instance
∀x 1 ∃x 2 ∀x 3 φ for φ =( x 1 ∨ x 2
x 3 ) ( x 1 ∨ x 2 ∨ x 3 ) ( x 1 ∨ x 2 ∨ x 3 ) of QUANTIFIED SATISFIABILITY .Theeightvaluesat
the leaves of the tree are the values of φ on the eight different assignments to ( x 1 , x 2 , x 3 ) .
 
Search WWH ::




Custom Search