Paper Info
Title
Realizable paths and the nl vs l problem
Abstract
A celebrated theorem of Savitch [63] states that NSPACE( S) ⊆ DSPACE(S2). In particular, Savitch gave a deterministic algorithm to solve ST-Connectivity (an NL-complete problem) using O(log 2n) space, implying NL ⊆ DSPACE(log2n). While Savitch's theorem itself has not been improved in the last four decades, several graph connectivity problems are shown to lie between L and NL, providing new insights into the space-bounded complexity classes. All the connectivity problems considered in the literature so far are essentially special cases of ST-Connectivity. In the first half of this thesis, we initiate the study of auxiliary PDAs as graph connectivity problems and define sixteen different graph realizability problems and study their relationships. The complexity of these connectivity problems lie between L and P. ST-Realizability, the most general graph realizability problem is P-complete. 1DSTREAL(poly), the most specific graph realizability problem is L-complete. As special cases of our graph realizability problems we define two natural problems, Balanced ST-Connectivity and Positive Balanced ST-Connectivity , that lie between L and NL. In the second half of this thesis, we study the space complexity of SGSLogCFL, a graph realizability problem lying between L and LogCFL. We define generalizations of graph squaring and transitive closure, present efficient parallel algorithms for SGSLogCFL and use the techniques of Trifonov [70] to show that SGSLogCFL is contained in DSPACE(lognloglog n). This implies that Balanced ST-Connectivity is contained in DSPACE(lognloglogn ). We conclude with several interesting new research directions.
Year
Venue
Keywords
2010
Realizable paths and the nl vs l problem
Balanced ST-Connectivity,realizable path,special case,graph realizability problem,Positive Balanced ST-Connectivity,st-connectivity,general graph realizability problem,auxiliary pushdown automata,savitch's theorem,graph connectivity problem,sixteen different graph realizability,NL-complete problem,specific graph realizability problem,logcfl,space-bounded computation,parallel graph algorithms,connectivity problem,symmetric turing machines.,nl vs l problem
DocType
Volume
Citations 
Journal
abs/1011.3840
0
PageRank 
References 
Authors
0.34
33
2
Name
Order
Citations
PageRank
Richard J. Lipton164121796.57
Shiva Kintali213314.00