Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-094 | 10th November 2004 00:00

Undirected ST-Connectivity in Log-Space



We present a deterministic, log-space algorithm that solves
st-connectivity in undirected graphs. The previous bound on the
space complexity of undirected st-connectivity was
log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and
Zhou. As undirected st-connectivity is
complete for the class of problems solvable by symmetric,
non-deterministic, log-space computations (the class SL), this
algorithm implies that SL=L (where L is the class of
problems solvable by deterministic log-space computations). Our
algorithm also implies log-space constructible universal-traversal
sequences for graphs with restricted labelling and log-space
constructible universal-exploration sequences for general graphs.

ISSN 1433-8092 | Imprint