Information Technology Reference
In-Depth Information
an edge from vertex
u
1
to vertex
u
2
if the last letter in the name associated with
u
1
is the first
letter in the name associated with
u
2
. In general this graph is directed because an edge from
u
1
to
u
2
does not guarantee an edge from
u
2
to
u
1
.
GENERALIZED GEOGRAPHY
Instance:
Adirectedgraph
G
=(
V
,
E
)
and a vertex
v
.
Answer:
“Yes” if there is a sequence of (at most
|
V
|
) alternating vertex selections by two
players such that vertex
v
is the first selection by the first player and for each selection of
the first player and all selections of the second player of vertices adjacent to the previous
selection, the second player arrives at a vertex from which it cannot select a vertex not
previously selected.
THEOREM
8.12.3
GENERALIZED GEOGRAPHY
is log-space complete for
PSPACE
.
Proof
To s h ow t h a t
GENERALIZED GEOGRAPHY
is log-space complete for
PSPACE
,we
show that it is in
PSPACE
and that
QUANTIFIED SATISFIABILITY
can be reduced to it
in log-space. To establish the first result, we show that the outcome of
GENERALIZED
GEOGRAPHY
can be determined by evaluating a graph similar to the binary tree used to
show that
QUANTIFIED SATISFIABILITY
is realizable in
PSPACE
.
Given the graph
G
=(
V
,
E
)
(see Fig.
8.18
(a)), we construct a search graph (see
Fig.
8.18
(b)) by performing a variant of depth-first search of
G
from
v
.Ateachvertex
we visit the next unvisited descendant, continuing until we encounter a vertex on the cur-
rent path, at which point we backtrack and try the next sibling of the current vertex, if any.
In depth-first search if a vertex has been visited previously, it is not visited again. In this
variant of the algorithm, however, a vertex is revisited if it is not on the current path. The
length of the longest path in this tree is at most
|
V
|−
1 because each path can contain no
|
V
|
|
V
|
more than
.
At a leaf vertex a player has no further moves. The first player wins if it is the second
player's turn at a leaf vertex and loses otherwise. Thus, a leaf vertex is labeled 1 (0) if the
first player wins (loses). To insure that the value at a vertex
u
is 1 if the two players reach
u
and the first player wins, we assign
OR
operators to vertices at which the first player makes
selections and
AND
operators otherwise. (The output of a one-input
AND
or
OR
gate is the
vertices. The tree may have a number of vertices exponential in
Marblehead
OR
Marblehead
Danvers
AND
AND
Dedham
OR
OR
OR
Danvers
Dedham
AND
AND
AND
Saugus
OR
0
OR
0
1
1
Salem Mansfield
(a)
(b)
Figure 8.18
(a) A graph for the generalized geography game and (b) the search tree associated
with the game in which the start vertex is Marblehead.
Search WWH ::
Custom Search