David Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum

We show that searching a width k maze is complete for \Pi_k, i.e., for

the k'th level of the AC^0 hierarchy. Equivalently, st-connectivity

for width k grid graphs is complete for \Pi_k. As an application,

we show that there is a data structure solving dynamic st-connectivity

for constant ...
more >>>

Eric Allender, Samir Datta, Sambuddha Roy

We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to ... more >>>

Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since

* reachability on grid graphs is logspace-equivalent to reachability in general planar digraphs, and

* reachability on certain classes of grid graphs gives ...
more >>>