Information Technology Reference
In-Depth Information
der complements), we have that every problem in
coPSPACE
can be reduced in log-space
to
QUANTIFIED SATISFIABILITY
. However, since
PSPACE
=
coPSPACE
,wehavethe
desired result.
Our task now is to show that every problem
P∈
PSPACE
can be reduced in log-space
to an instance of
QUANTIFIED UNSATISFIABILITY
.Let
L
∈
PSPACE
be the language
and let
M
be the DTM deciding
L
. Instances of
QUANTIFIED
UNSATISFIABILITY
will be quantified formulas in SOPE form that describe conditions on
the configuration graph
G
(
M
,
w
)
of
M
on input
w
. We associate a Boolean vector with
each vertex in
G
(
M
,
w
)
and assume that
G
(
M
,
w
)
has one initial and final vertex associated
with the vectors
a
and
b
, respectively. (We can make the last assumption because
M
can be
designed to enter a cleanup phase in which it prints blanks in all non-blank tape cells.)
Let
c
and
d
be vector encodings of arbitrary configurations
c
and
d
of
G
(
M
,
w
)
.We
construct formulas
ψ
i
(
c
,
d
)
,0
P
of “Yes” instances of
k
, in SOPE form that are satisfied if and only if
there exists a path from
c
to
d
in
G
(
M
,
w
)
of length at most 2
i
(it computes the predi-
cate PATH(
c
,
d
,2
i
) introduced in the proof of Theorem
8.5.5
). Then a “Yes” instance of
QUANTIFIED UNSATISFIABILITY
is the formula
ψ
k
(
a
,
b
)
,where
a
and
b
are encodings
of the initial and final vertices of
G
(
M
,
w
)
for
k
sufficiently large that a polynomial-space
computation can be done in time 2
k
. Since, as seen in Theorem
8.5.6
, a deterministic com-
putation in space
S
is done in time
O
(
2
S
)
,itsufficesfor
k
to be polynomial in the length
of the input.
The formula
ψ
0
(
c
,
d
)
is satisfiable if either
c
=
d
or
d
follows from
c
in one step. Such
formulas are easily computed from the descriptions of
M
and
w
.
ψ
i
(
c
,
d
)
can be expressed
as shown below, where the existential quantification is over all possible intermediate config-
urations
e
of
M
. (See the proof of Theorem
8.5.5
for the representation of PATH(
c
,
d
,2
i
)
in terms of PATH(
c
,
e
,2
i−
1
)andPATH(
e
,
d
,2
i−
1
).)
≤
i
≤
ψ
i
(
c
,
d
)=
∃
e
[
ψ
i−
1
(
c
,
e
)
∧
ψ
i−
1
(
e
,
d
)]
(8.1)
Note that
e
q
,where
q
is the length of
e
. Universal quantifi-
cation over a vector is expanded in a similar fashion.
Unfortunately, for
i
=
k
this recursively defined formula requires space exponential
in the size of the input. Fortunately, we can represent
ψ
i
(
c
,
d
)
more succinc
tl
y using the
implication operator
x
∃
e
is equivalent to
∃
e
1
∃
e
2
···∃
⇒
y
, as shown below, where
x
⇒
y
is equivalent to
x
∨
y
.Note
that if
x
⇒
y
is
TRUE
, then either
x
is
FALSE
or
x
and
y
are both
TRUE
.
ψ
i
(
c
,
d
)=
∃
e
[
∀
x
∀
y
[(
x
=
c
∧
y
=
e
)
∨
(
x
=
e
∧
y
=
d
)]
⇒
ψ
i−
1
(
x
,
y
)]
(8.2)
Here
x
=
y
denotes
(
x
1
=
y
1
)
∧
(
x
2
=
y
2
)
∧···∧
(
x
q
=
y
q
)
,where
(
x
i
=
y
i
)
denotes
x
i
y
i
∨
x
i
y
i
. Then, the formula in the outer square brackets of (
8.2
) is true when either
(
x
=
c
y
=
d
)
is
FALSE
or this expression is
TRUE
and
ψ
i−
1
(
x
,
y
)
is
also
TRUE
. Because the contents of the outer square brackets are
TRUE
, the quantization on
x
and
y
requires that
ψ
i−
1
(
c
,
e
)
and
ψ
i−
1
(
e
,
d
)
both be
TRUE
or that the formula given
in (
8.1
) be satisfied.
It remains to convert the expression for
ψ
i
(
c
,
d
)
given above to SOPE form in log-space.
Butthisisstraightforward.Wereplace
g
∧
y
=
e
)
∨
(
x
=
e
∧
⇒
h
by
g
∨
h
,where
g
=(
r
∧
s
)
∨
(
t
∧
u
)
and
r
=(
x
=
c
),
s
=(
y
=
e
)
,
t
=(
x
=
e
)
,and
u
=(
y
=
d
)
. It follows that
g
=(
r
∨
s
)
∧
(
t
∨
u
)
=(
r
∧
t
)
∨
(
r
∧
u
)
∨
(
s
∧
t
)
∨
(
s
∧
u
)
Search WWH ::
Custom Search