Information Technology Reference
In-Depth Information
THEOREM
8.5.5
(Savitch)
REACHABILITY
is in
SPACE
(log
2
n
)
.
Proof
As mentioned three paragraphs earlier, the
REACHABILITY
problem on a graph
G
=
(
V
,
E
)
can be solved with depth-first search. This requires storing data on each vertex visited
during a search. This data can be as large as
O
(
n
)
,
n
=
|
V
|
. We exhibit an algorithm that
uses much less space.
Given an instance of
REACHABILITY
defined by
G
=(
V
,
E
)
and
u
,
v
∈
V
,foreach
we define predicates PATH
a
,
b
,2
k
whose
value is true if there exists a path from
a
to
b
in
G
whose length is at most 2
k
and false other-
wise. Since no path has length more than
n
, the solution to the
REACHABILITY
problem is
pair of vertices
(
a
,
b
)
and integer
k
≤
log
2
n
the value of PATH
u
,
v
,2
log
2
n
. The predicates PATH
a
,
b
,2
0
aretrueifeither
a
=
b
or there is a path of length 1 (an edge) between the vertices
a
and
b
.Thus,PATH
a
,
b
,2
0
can be evaluated directly by consulting the problem instance on the input tape.
The algorithm that computes PATH
u
,
v
,2
log
2
n
with space
O
(log
2
n
)
uses the
fact that any path of length at most 2
k
can be decomposed into two paths of length at
most 2
k−
1
.Thus,ifPATH
a
,
b
,2
k
is true, then there must be some vertex
z
such that
PATH
a
,
z
,2
k−
1
and PATH
z
,
b
,2
k−
1
are both true. The truth of PATH
a
,
b
,2
k
can
be established by searching for a
z
such that PATH
a
,
z
,2
k−
1
is true. Upon finding one,
we determine the truth of PATH
z
,
b
,2
k−
1
. Failing to find such a
z
,PATH
a
,
b
,2
k
is
declared to be false. Each evaluation of a predicate is done in the same fashion, that is, re-
cursively. Because we need evaluate only one of PATH
a
,
z
,2
k−
1
and PATH
z
,
b
,2
k−
1
at a time, space can be reused.
We now describe a deterministic Turing machine with an input tape and two work tapes
computing PATH
u
,
v
,2
log
2
n
. The input tape contains an instance of
REACHABILITY
,
which means it has not only the vertices
u
and
v
but also a description of the graph
G
.The
first work tape will contain triples of the form (
a
,
b
,
k
), which are called
activation records
.
This tape is initialized with the activation record (
u
,
v
,
). (See Fig.
8.5
.)
The DTM evaluates the last activation record, (
a
,
b
,
k
), on the first work tape as de-
scribed above. There are three kinds of activation records,
complete records
of the form
(
a
,
b
,
k
),
initial segments
of the form (
a
,
z
,
k
log
2
n
−
1), and
final segments
of the form (
z
,
b
,
k
−
1). The first work tape is initialized with the complete record (
u
,
v
,
).
An initial segment is created from the current complete record (
a
,
b
,
k
)
by selecting a
vertex
z
to form the record (
a
,
z
,
k
log
2
n
1), which becomes the current complete record. If
it evaluates to true, it can be determined to be an initial or final segment by examining the
previous record (
a
,
b
,
k
). If it evaluates to false, (
a
,
z
,
k
−
1
)
is erased and another value
of
z
, if any, is selected and another initial segment placed on the work tape for evaluation.
If no other
z
exists, (
a
,
z
,
k
−
1
)
is erased and the expression PATH
a
,
b
,2
k
is declared
−
false. If (
a
,
z
,
k
1
)
is created, placed on the
work tape, and evaluated in the same fashion. As mentioned in the second paragraph of this
−
1
)
evaluates to true, the final record (
z
,
b
,
k
−
...
(
uv
d
)
(
u
z
d
−
)
(
z
x
d
−
)
1
2
Figure 8.5
A snapshot of the stack used by the
REACHABILITY
algorithm in which the com-
ponents of an activation record (
a
,
b
,
k
) are distributed over several cells.
Search WWH ::
Custom Search