Information Technology Reference
In-Depth Information
2
(
k
+
1
)
≥
log
n
and
l
Setting
μ
=
=
log
2
ʲ
,
we
get an algorithm for SPATH with
2
(
k
+
1
)
≥
log
n
(
log
ʲ
+
1
)
×
2
log
ʲ
×
time complexity
T
(
n
, ʲ)
=
O
(
n
)
and space complexity
n
2
(
k
+
1
)
≥
log
n
S
(
n
, ʲ)
=
O
(
×
log
ʲ)
.
2
k
≥
log
n
, this results in polynomial time and space
O
n
giving an
algorithm for the reachability problem with polynomial running time and
O
For
ʲ
=
(
2
k
≥
log
n
)
n
(
2
k
≥
log
n
)
space bound.
Acknowledgments
I would like to thank Pavan Aduri for extended collaboration and discussions
on the reachability problem, and for his valuable comments on an earlier draft of this article.
I would like to thank the organizers, V. Arvind and Manindra Agrawal, of the Complexity and Logic
Workshop at IIT Kanpur (in celebration of the 60th birthday of Somenath Biswas) for inviting me
to give a talk at the workshop.
References
[ABC+09] E. Allender, D.A. Barrington, T. Chakraborty, S. Datta, S. Roy, Planar and grid graph
reachability problems. Theor. Comput. Syst.
45
(4), 675-723 (2009)
[AD11] T. Asano, B. Doerr, in
Memory-constrained algorithms for shortest path problem
.
(CCCG, 2011), pp. 135-138
[ADR05] E. Allender, S. Datta, S. Roy, in
The Directed Planar Reachability Problem
(FSTTCS,
2005), pp. 238-249
[ÀJ93] C. Àlvarez, B. Jenner, A very hard log-space counting class. Theor. Comput. Sci.
107
,
3-30 (1993)
[AM08] V. Arvind, P. Mukhopadhyay. Derandomizing the isolation lemma and lower bounds
for circuit size. In APPROX-RANDOM (2008), pp. 276-289
[ARZ99] E. Allender, K. Reinhardt, S. Zhou, Isolation, matching, and counting uniform and
nonuniform upper bounds. J. Comput. Syst. Sci.
59
(2), 164-181 (1999)
[BBRS98] G. Barnes, J.F. Buss, W.L. Ruzzo, B. Schieber, A sublinear space, polynomial time
algorithm for directed s- t connectivity. SIAM J. Comput.
27
(5), 1273-1282 (1998)
[BJLR91] G. Buntrock, B. Jenner, K. Lange, P. Rossmanith, Unambiguity and fewness for loga-
rithmic space, in
8th International Symposium on Fundamentals of Computation Theory
(1991), pp. 168-179
[BTV09] C. Bourke, R. Tewari, N.V. Vinodchandran, Directed planar reachability is in unam-
biguous logarithmic space. ACM Trans. Comput. Theor.
1
(1), 1-17 (2009)
[CR80] S.A. Cook, C. Rackoff, Space lower bounds for maze threadability on restricted
machines. SIAM J. Comput.
9
(3), 636-652 (1980)
[EPA99] J. Edmonds, C.K. Poon, D. Achlioptas, Tight lower bounds for st-connectivity on the
NNJAG model. SIAM J. Comput.
28
(6), 2257-2284 (1999)
[GM87] H. Gazit, G.L. Miller,
A parallel algorithm for finding a separator in planar graphs
(FOCS, 1987), pp. 238-248
[Imm88] N. Immerman, Nondeterministic space is closed under complementation. SIAM J.
Comput.
17
(5), 935-938 (1988)
[INP+13] T. Imai, K Nakagawa, A. Pavan, N. V. Vinodchandran, O. Watanabe, A
n
1
/
2
+
˃
-space
and polynomial-time algorithm for directed planar reachability, in
Conference on Com-
putational Complexity
(2013), pp. 277-286
[KV10] J. Kyncl, T. Vyskocil, Logspace reduction of directed reachability for bounded genus
graphs to the planar case. ACM Trans. Comput. Theor.
1
(3), 1-11 (2010)
[MVV87] K. Mulmuley, U. Vazirani, V. Vazirani, Matching is as easy as matrix inversion.
Cominatorica
7
(1), 105-113 (1987)
