Information Technology Reference
In-Depth Information
non-deterministic log-space (
NL
). The breakthrough result of Reingold implies that
the undirected reachability problem characterizes the complexity of deterministic
log-space (
L
)[
Rei08
]. It is also known that a certain restricted promise version of
the reachability problem over directed graphs characterizes randomized log-space
computations (
RL
)[
RTV06
]. Clearly, progress in space complexity studies is directly
related to progress in understanding graph reachability problems.We refer the readers
to an excellent (albeit two decades old) survey by Avi Wigderson [
Wig92
] to further
understand the significance of reachability problems in complexity theory.
This article is far from an exhaustive survey on the space complexity of the graph
reachability problem. In particular, some of the major progress (such as Reingold's
algorithm for undirected graph reachability and Saks and Zhou's deterministic simu-
lation of randomized log-space) are not discussed here. Instead, we limit our discus-
sion to some recent progress that the author and his collaborators reported on these
questions for certain subclasses of surface-embedded directed graphs. It is mostly an
elaboration of the talk that the author gave on Prof. Somenath Biswas's 60th birthday
celebrations at IIT Kanpur in August of 2012.
3.1.1 Three Central Questions
We first discuss three central questions concerning the space complexity of the
directed graph reachability problem. These are well-known and difficult open ques-
tions in the area, and progress on any of these is a step towards the much bigger
NL
versus
L
question (the first two problems are discussed in Wigderson's 1992
survey [
Wig92
]). However, the author feels that the known barriers for attacking
these problems are much less severe than those known for many difficult open prob-
lems in time-bounded complexity classes and circuit lower bounds, and believes that
breakthrough progress on these problems can be made in the near future.
Problem 1: Improving Savitch's bound.
About four decades ago Savitch proved
that the reachability problem over directed graphs with
n
vertices can be solved
in space
O
log
2
n
deterministically [
Sav70
]. This implies that problems that can
be solved nondeterministically in space
s
(
)
(
n
)
have
deterministic
algorithms with
s
2
space bound. Thus, for polynomial space bounds, nondeterminism does
not add any additional power to determinism. For the important case when the space
bound is
O
O
(
(
n
))
, Savitch's theorem implies that all problems in
NL
can be solved
deterministically in
O
(
log
n
)
log
2
n
space.
Is this quadratic blow-up necessary?
This is
one of the most important open problems in this topic.
(
)
Problem 2: Improving the BBRS bound.
The time complexity of Savitch's algorithm
is
n
log
n
—a super-polynomial bound. The standard breadth first search algorithm
(BFS) is another fundamental algorithm for solving graph reachability. BFS can be
implemented in linear time but requires linear space. BFS is efficient in time but not in
space, and Savitch's algorithm is efficient in space but takes super-polynomial time.
Hence a natural and significant question that researchers have considered is whether
ˇ(
)
