This paper introduces logspace optimisation problems as analogues of the well-studied polynomial-time optimisation problems. Similarly to them, logspace optimisation problems can have vastly different approximation properties, even though the underlying existence and budget problems have the same computational complexity. Numerous natural problems are presented that exhibit such a varying complexity. ... more >>>

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), ... more >>>