Information Technology Reference
In-Depth Information
value of its input.) This provides a circuit that can be evaluated just as was the circuit
C
qsat
used in the proof of Theorem
8.12.1
. The “Yes” instances of
GENERALIZED GEOGRAPHY
are such that the first player can win by choosing a first city. In Fig.
8.18
the value of the
root vertex is 0, which means that the first player loses by choosing to start with Marblehead
as the first city.
Vertices labeled
AND
or
OR
in the tree generated by depth-first search can have arbitrary
in-degree because the number of vertices that can be reached from a vertex in the original
graph is not restricted. The procedure
tree eval
described in the proof of Theorem
8.12.1
can be modified to apply to the evaluation of this DAG whose vertex in-degree is potentially
unbounded. (See Problem
8.30
.) This modified procedure runs in space polynomial in the
size of the graph
G
.
We now show that
ALTERNATING QUANTIFIED SATISFIABILITY
(abbreviated
AQSAT
)
can be reduced in log-space to
GENERALIZED GEOGRAPHY
. Given an instance of
AQSAT
such as that shown below, we construct an instance of
GENERALIZED GEOGRAPHY
,as
shown in Fig.
8.19
. We assume without loss of generality that the number of quantifiers is
even. If not, add a dummy variable and quantify on it:
∃
x
1
∀
x
2
∃
x
3
∀
x
4
[(
x
1
∨
x
2
∨
x
3
)
∧
(
x
1
∨
x
2
∨
x
3
)
∧
(
x
1
∨
x
2
∨
x
3
)
∧
(
x
4
∨
x
4
)]
t
x
1
x
1
x
1
1
0
m
m
x
2
x
2
x
2
1
0
m
m
x
3
x
3
x
3
1
0
m
m
x
4
x
4
x
4
1
0
b
x
1
∨
x
2
∨
x
3
x
1
∨
x
2
∨
x
3
x
1
∨
x
2
∨
x
3
x
4
∨
x
4
Figure 8.19
An instance of
GENERALIZED GEOGRAPHY
corresponding to an instance of
ALTERNATING QUANTIFIED SATISFIABILITY
.
Search WWH ::
Custom Search