Information Technology Reference
In-Depth Information
proof, (
a
,
b
, 0) is evaluated by consulting the description of the graph on the input tape. The
second work tape is used for bookkeeping, that is, to enumerate values of
z
and determine
whether a segment is initial or final.
The second work tape uses space
O
(log
n
)
. The first work tape contains at most
activation records. Each activation record
(
a
,
b
,
k
)
can be stored in
O
(log
n
)
space
because each vertex can be specified in
O
(log
n
)
space and the depth parameter
k
can be
specified in
O
(log
k
)=
O
(log log
n
)
space. It follows that the first work tape uses at most
O
(log
2
n
)
space.
log
2
n
The following general result, which is a corollary of Savitch's theorem, demonstrates that
nondeterminism does not enlarge the space complexity classes if they are defined by space
bounds that are at least logarithmic. In particular, it implies that
PSPACE
=
NPSPACE
.
COROLLARY
8.5.1
Let
r
(
n
)
be a proper Turing computable function
r
:
→
satisfying
r
(
n
)=Ω(log
n
)
.Then
NSPACE
(
r
(
n
))
⊆
SPACE
(
r
2
(
n
))
.
Proof
Let
M
ND
be an NDTM with input and output tapes and
s
work tapes. Let it recog-
nize a language
L
NSPACE
(
r
(
n
))
. For each input string
w
, we generate a configuration
graph
G
(
M
ND
,
w
)
of
M
ND
.(SeeFig.
8.6
.) We use this graph to determine whether or not
w
∈
states, each tape cell can have at most
c
values (there are
c
(
s
+
2
)
r
(
n
)
configurations for the
s
+
2tapes),the
s
work tape heads and the output tape
head can assume values in the range 1
∈
L
.
M
ND
has at most
|
Q
|
r
(
n
)
, and the input head
h
s
+
1
can assume
one of
n
positions (there are
nr
(
n
)
s
+
1
configurations for the tape heads). It follows that
M
ND
has at most
≤
h
j
≤
k
log
n
+
r
(
n
)
configurations.
G
(
M
ND
,
w
)
has the same number of vertices as there are configurations and a number of edges at most
thesquareofitsnumberofvertices.
Let
L
c
(
s
+
2
)
r
(
n
)
(
nr
(
n
)
s
+
1
)
|
Q
|
≤
NSPACE
(
r
(
n
))
be recognized by an NDTM
M
ND
. We describe a determin-
istic
r
2
(
n
)
-space Turing machine
M
D
recognizing
L
. For input string
w
∈
L
of length
n
,
this machine solves the
REACHABILITY
problem on the configuration graph
G
(
M
ND
,
w
)
of
M
ND
described above. However, instead of placing on the input tape the entire configu-
ration graph, we place the input string
w
and the description of
M
ND
. We keep configura-
tions on the work tape as part of activation records (they describe vertices of
G
(
M
ND
,
w
)
).
∈
Figure 8.6
The acyclic configuration graph
G
(
M
ND
,
w
)
of a nondeterministic Turing machine
M
ND
on input
has one vertex for each configuration of
M
ND
. Here heavy edges identify the
nondeterministic choices associated with a configuration.
w
Search WWH ::
Custom Search