Information Technology Reference
In-Depth Information
istic time classes are closed under complement. As we shall see, this is intimately related to the
question
P
=
NP
.
As stated in Definition
5.2.1
, for no choices of moves is an NDTM allowed to produce an
answer for which it is not designed. In particular, when computing a function it is not allowed
to give a false answer for any set of nondeterministic choices.
THEOREM
8.6.2
(Immerman-Szelepscenyi)
Given a graph
G
=(
V
,
E
)
and a vertex
v
,the
number of vertices reachable from
v
can be computed by an NDTM in space
O
(log
n
)
,
n
=
|
V
|
.
Proof
Let
V
=
. Any node reachable from a vertex
v
must be reachable via a
path of length (number of edges) of at most
n
{
1, 2,
...
,
n
}
.Let
R
(
k
,
u
)
be the number
of vertices of
G
reachable from
u
by paths of length
k
or less. The goal is to compute
R
(
n
−
1,
n
=
|
V
|
1,
u
)
. A deterministic program for this purpose could be based on the predicate
PATH
(
u
,
v
,
k
)
that has value 1 if there is a path of length
k
or less from vertex
u
to vertex
v
and 0 otherwise and the predicate
ADJACENT
-
OR
-
IDENTICAL
(
x
,
v
) that has value 1 if
x
=
v
or there is an edge in
G
from
x
to
v
and 0 otherwise. (See Fig.
8.8
.) If we let the
vertices be associated with the integers in the interval
[
1,
...
,
n
]
,then
R
(
n
−
−
1,
u
)
can be
evaluated as follows:
1,
u
)=
1
R
(
n
−
PATH
(
u
,
v
,
n
−
1
)
≤v≤n
=
1
PATH
(
u
,
x
,
n
−
2
)
ADJACENT
-
OR
-
EQUAL
(
x
,
v
)
≤v≤n
≤x≤n
1
1,
u
)
is converted to a program, the amount of storage
needed grows more rapidly than
O
(log
n
)
. However, if the inner use of PATH
(
u
,
x
,
n
When this description of
R
(
n
−
−
2
)
is replaced by the nonrecursive and nondeterministic test
EXISTS
-
PATH
-
FROM
-
u
-
TO
-
v
-
≤
LENGTH
of Fig.
8.9
for a path from
u
to
x
of length
n
2, then the space can be kept to
O
(log
n
)
. This test nondeterministically guesses paths but verifies deterministically that all
paths have been explored.
The procedure
COUNTING
-
REACHABILITY
of Fig.
8.9
is a nondeterministic program
computing
R
(
n
−
-
DISTANCE
-
FROM
-
u
to compute the number of vertices at distance
dist
or less from
u
in order of increasing
values of
dist
.(Itcomputes
dist
correctly or fails.) This procedure has
prev num dist
as a parameter, which is the number of vertices at distance
dist
−
1,
u
)
. tusestheprocedure#-
VERTICES
-
AT
-
≤
−
1 or less. It passes this
v
x
=
v
x
u
u
(b)
Figure 8.8
Paths explored by the
REACHABILITY
algorithm. Case (a) applies when
x
and
v
are
different and (b) when they are the same.
(a)
Search WWH ::
Custom Search