Savitch's Theorem

1 Savitch’s Theorem
We’ll prove an amazing result: Nondeterministic space algorithms can be simulated e

伍 - ciently by deterministic space algorithms, with only quadratic loss in space usage.
That is, nondeterminism does not give us extra power in the case of space-bounded
computation!
Recall that NL = NSpace(log n), and NPSPACE = ∪k NSpace(nk ).
First, using the notion of coniguration graphs, we can show the following.
Theorem 1. NL P
Proof. The proof is exactly the same as that for L P.
Coniguration graphs of space-bounded TMs are a very useful tool for analyzing
space- bounded computation. As the next theorem shows a reachability problem for
graphs exactly captures the complexity of the class NL.
Deine ST - CON = {(G,s,t) | G is a directed graph with a path from s to t}.
Theorem 2. ST-CON is NL-complete under logspace reductions.
Remark: Note that we restricted the class of reductions to logspace computable

ones. This is necessary to make the notion NL-completeness nontrivial. (As you recall
from Prob- lem Set 1, basically every language in P is P-complete under polytime
reductions.)
Proof. 1. ST - CON ∈ NL: Given a graph G = (V, E) and s,t ∈ V ,

nondeterministically
guess a path from s to t, by keeping track of a current vertex on a path and a
next vertex on a path. After guessing a next vertex on a path, make it the new
current vertex (erasing the old current vertex) so as to re-use the space, and run
in O(log n) space only. If ever t is a current vertex on a guessed path, then Accept.
2. ST - CON is NL-hard: Given any language L ∈ NL decided by some logspace

NTM M, and an input x, construct the coniguration graph of M on x. This can be
done in logspace (can you see why?) Make s to be the start coniguration, and t
the accepting coniguration. (Note: we can always modify any given NTM so that
1
it has only one accepting coniguration: after entering qaccept , the machine will
erase all of its work- tapes, and go to the irst non-blank symbol of its input
tape.)
Another representation of NL, which suggested to Immerman the idea of the proof
of NL = coNL (which we will do later today), is irst-order logic with a transitive
closure operator. Transitive closure is essentially reachability: a pair of vertices (s,t)
is in the
1
transitive closure of a graph if t is reachable from s. In the logic form, transitive closure
of a relation E is X satisfying the following:
X 0 (u,v) —E(u,v) Λ u = v
Xi+1 (u,v) —二 z < nXi (u,z) V Xi (z, v)
That is, it is the smallest value of X such that Xi+1 = Xi. In a more general case,
instead of the edge relation E we can put any irst-order formula φ, which may have X
as a free variable.
Recall from the proof of Fagin’s theorem that the correctness of a run of a Turing
machine can be described by a irst-order formula (with arithmetic operators). Now,
together with the fact that a computation of an NL machine can be thought of as a
reachability in its coniguration graph, it is easy to see that FO(TC) (irst-order with
transitive closure) captures NL.
Theorem 3 (Savitch’s Theorem). ST 一 CON e Space(log n ) .

2
Corollary 4. 1. NL Space(log2 n).
2. NPSPACE = PSPACE.
2
Proof of Savitch’s Theorem. We will design a log n-space algorithm that, given a
directed graph G = (V, E) with |V | = n nodes, and s,t e V , will accept if t is
reachable from s. (For convenience, we assume that (u,u) e E for every node u e V.)
The idea of the proof is similar to the second line of the deinition of transitive closure.
We design algorithm Path(x,y, i) which accepts if there is a path from x to y of
length at most 2i. Note that t is reachable from s if Path(s,t,log n) accepts. (Do you
see why?)
Algo Path(x,y, i)
if i = 0 then
Accept if (x,y) e E
end if
for every z e V
if Path(x,z, i 一 1) accepts AND
Path(z,y, i 一 1) accepts % we re-use space here!
then Accept
end if
end for
2
Reject % if no “middle” point z was found, we reject
end Algo
It is not hard to see that algorithm Path is correct. To analyze the space used,
note that the depth of the recursion is log n, and that the size of each“stack record”
during the
recursion is the size of (x,y, i) e O(log n). Thus, the total space used is O(log2 n).
2
It is still a big open problem to decide if NL = L. To show this, it would su 伍 ce to
give a deterministic logspace algorithm for ST-CON, the problem of st-connectivity for
directed graphs on n vertices. Interestingly, Reingold has recently showed that the st-
connectivity problem for undirected graphs is solvable in detereministic logspace! The
algorithm for doing this is highly nontrivial and not at all obvious; it is based on the
algebraic characterization of connectivity in graphs (in terms of the so-called eigenvalue
gap, the diference between the two largest eigenvalues of the adjacency matrix of a
given graph). This algorithmic success renewed the interest in the NL vs. L question.
Next we will see another surprising result showing that NL = coNL, something we
don’t expect to be true in the setting of time complexity classes. (This might be taken
as another piece of evidence pointing to the possibility of NL = L...)

Savitch's Theorem

Uploaded by

Copyright:

Available Formats

Savitch's Theorem

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Savitch's Theorem

Uploaded by

Copyright:

Available Formats

1 Savitch’s Theorem

We’ll prove an amazing result: Nondeterministic space algorithms can be simulated e

Proof. The proof is exactly the same as that for L P.

Theorem 2. ST-CON is NL-complete under logspace reductions.

Remark: Note that we restricted the class of reductions to logspace computable

Proof. 1. ST - CON ∈ NL: Given a graph G = (V, E) and s,t ∈ V ,

2. ST - CON is NL-hard: Given any language L ∈ NL decided by some logspace

Theorem 3 (Savitch’s Theorem). ST 一 CON e Space(log n ) .

Corollary 4. 1. NL Space(log2 n).

You might also like