Title | : | Complexity theoretic Aspects of L-reachability |
Speaker | : | K.S. Sunil (IITM) |
Details | : | Tue, 22 Sep, 2015 2:00 PM @ BSB 361 |
Abstract: | : | Reachability problems in mathematical structures are a well-studied problem in space complexity. An important example is the graph reachability problem where given a graph G and two special vertices s and t, is there a path from s to t in the graph G. This problem exactly captures the space complexity of problems solvable in nondeterministic logarithmic space. A natural extension of the problem using formal language theory is the L-reachability problem : Fix a language L defined over a finite alphabet A. Given a graph whose edges are labelled by alphabet symbols and two special vertices s and t, test if there is path from s to t in the graph such that the concatenation of the symbols seen from s to t in the path, forms a string in the language L. Although the original motivation to study this problem is its application in the optimisation and parallelisation phases of compiler design, in this work, we take a complexity theoretic view. By restricting the language using formal language theory, we show that the complexity of L-reachability increases with the power of the formal language class. We show that there is a regular language for which the L-reachability problem is NLOG-complete even for undirected graphs. In the case of linear languages, the complexity of L-reachability does not go beyond the complexity of L itself. Further, there is a deterministic context-free language L for which L-DAGREACH is LogCFL-complete. We use L-reachability as a lens to study structural complexity. In this direction we show that there is a language A in LOG for which A-DAGREACH is NP-complete. Using this we show that P vs NP question is equivalent to P vs DAGREACH^{-1}(P) question. This leads to the intriguing possibility that by proving DAGREACH^{-1}(P) is contained in some subclass of P, we can prove an upward translation of separation of complexity classes. Note that, currently a way to upward translate the separation of complexity classes is not known. |