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