Information Technology Reference
In-Depth Information
we can design an algorithm for the directed graph reachability problem that is efficient
in both time and space. In particular, can we design a polynomial-time algorithm
for the directed graph reachability problem that uses only
O
n
1
−
˃
)
space for some
constant
˃
? The best known result in this direction is the two decades old bound due
to Barnes et al. [
BBRS98
] (which we call the BBRS bound). By cleverly combining
BFS and Savitch's algorithm, Barnes et al. designed a polynomial-time algorithm for
reachability that uses space
O
(
2
≥
log
n
—a slightly sub-linear function. Improving
the BBRS bound remains another significant open question regarding the space
complexity of the directed reachability problem.
(
n
/
)
Problem 3: NL versus UL Problem.
UL
denotes an unambiguous subclass of
NL
.
A decision problem
L
is in
UL
if and only if there exists a nondeterministic log-
space machine
M
deciding
L
such that, for every instance
x
,
M
has at most one
accepting computation on input
x
[
BJLR91
,
ÀJ93
]. Thus
UL
is a complexity class
that is sandwiched between
NL
and
L
.Is
NL
UL
? While typically such collapse
results are unlikely in complexity theory (and even if they are likely, they are nearly
impossible to prove), there is an increasing body of evidence that in this specific
case the answer is yes, and the author believes that we might be able to prove this
equality using known techniques. Reinhardt and Allender showed using the isolation
lemma that in the nonuniform setting
NL
coincides with
UL
; that is
NL
=
/
poly
=
UL
poly
[
RA00
]. Further, in a subsequent paper, Allender, Reinhardt, and Zhou
showed that, under a certain hardness assumption the construction given in [
RA00
]
can be
derandomized
to show that
NL
/
=
UL
[
ARZ99
]. Thus it is very likely (at
least to the author) that
NL
=
UL
, though we do not yet have a proof. Can we show
NL
=
UL
unconditionally?
3.1.2 Outline
In the next two sections we discuss some progress that we have made towards these
three open questions—Sect.
3.2
on Problems 1 and 2, and Sect.
3.3
on the
NL
versus
UL
problem. All the results discussed in these sections are for directed graphs embed-
ded on topological surfaces. As an aside, in Sect.
3.4
we reproduce the proof of the
BBRS bound from [
BBRS98
], partly to bring more attention to this nice algorithm.
3.2 Space Efficient Reachability Algorithms for Graphs
with Topological Structure
An important sub-case of Problem 1 (and Problem 2) is to design reachability algo-
rithms that beat Savitch's bound (respectively, the BBRS bound) for directed graphs
with some topological structure (graphs that are embedded on topological surfaces).
We discuss some recent progress reported along this direction. The main results are
