Realizable Paths and the NL vs L Problem - Computer Science > Computational ComplexityReport as inadecuate

Realizable Paths and the NL vs L Problem - Computer Science > Computational Complexity - Download this document for free, or read online. Document in PDF available to download.

Abstract: A celebrated theorem of Savitch states that NSPACES is contained inDSPACES^2. In particular, Savitch gave a deterministic algorithm to solveST-CONNECTIVITY an NL-complete problem using Olog^2{n} space, implying NLis in DSPACElog^2{n}. While Savitch-s theorem itself has not been improved inthe last four decades, studying the space complexity of several special casesof ST-CONNECTIVITY has provided new insights into the space-bounded complexityclasses.In this paper, we introduce new kind of graph connectivity problems which wecall graph realizability problems. All of our graph realizability problems aregeneralizations of UNDIRECTED ST-CONNECTIVITY. ST-REALIZABILITY, the mostgeneral graph realizability problem, is LogCFL-complete. We define thecorresponding complexity classes that lie between L and LogCFL and study theirrelationships.As special cases of our graph realizability problems we define two naturalproblems, BALANCED ST-CONNECTIVITY and POSITIVE BALANCED ST-CONNECTIVITY, thatlie between L and NL. We present a deterministic Olognloglogn space algorithmfor BALANCED ST-CONNECTIVITY. More generally we prove that SGSLogCFL, ageneralization of BALANCED ST-CONNECTIVITY, is contained inDSPACElognloglogn. To achieve this goal we generalize several concepts suchas graph squaring and transitive closure and algorithms such as parallelalgorithms known in the context of UNDIRECTED ST-CONNECTIVITY.

Author: Shiva Kintali


Related documents