On the Complexity of L-reachability

• Autorzy: Komarath B. , Sarma J. , Sunil K. S.

Identyfikatory

DOI

10.3233/FI-2016-1371

• Języki publikacji: EN

Abstrakty

EN

We initiate a complexity theoretic study of the language based graph reachability problem (L-REACH) : Fix a language L. Given a graph whose edges are labelled with alphabet symbols of the language L and two special vertices s and t, test if there is path P from s to t in the graph such that the concatenation of the symbols seen from s to t in the path P forms a string in the language L. We study variants of this problem with different graph classes and different language classes and obtain complexity theoretic characterizations for all of them. Our main results are the following: • Restricting the language using formal language theory we show that the complexity of L- REACH increases with the power of the formal language class. We show that there is a regular language for which the L-REACH is NL-complete even for undirected graphs. In the case of linear languages, the complexity of L-REACH 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-REACH as a lens to study structural complexity. In this direction we show that there is a language A in TC⁰ 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 we do not know a way to upward translate the separation of complexity classes.

Słowa kluczowe

EN

CFL-reachability; L-reachability; structural complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 4
• Strony: 471--483
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Komarath B.

• Department of Computer Science & Engineering, Indian Institute of Technology Madras, Chennai 36, India

autor

Sarma J.

• Department of Computer Science & Engineering, Indian Institute of Technology Madras, Chennai 36, India

autor

Sunil K. S.

• Department of Computer Science & Engineering, Indian Institute of Technology Madras, Chennai 36, India

Bibliografia

• [1] Reingold O. Undirected connectivity in log-space. Journal of the ACM. 2008;55(4).
• [2] Barrington DAM. Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1. Journal of Computer and System Sciences. 1989;38(1):150–164. Available from: http://dx.doi.org/10.1016/0022-0000(89)90037-8.
• [3] Hansen KA. Constant Width Planar Computation Characterizes ACC0. In: Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science; 2004. p. 44–55. Available from: http://dx.doi.org/10.1007/978-3-540-24749-4_5.
• [4] Barrington DAM, Lu CJ, Miltersen PB, Skyum S. Searching constant width mazes captures the AC0 hierarchy. In: In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science. Springer-Verlag; 1998. p. 73–83.
• [5] Reps TW. On the Sequential Nature of Interprocedural Program-Analysis Problems. Acta Informatica. 1996;33(8):739–757. Available from: http://dx.doi.org/10.1007/BF03036473.
• [6] Reps TW. Program analysis via graph reachability. Information & Software Technology. 1998;40(11-12):701–726. Available from: http://dx.doi.org/10.1016/S0950-5849(98)00093-7.
• [7] Yannakakis M. Graph-Theoretic Methods in Database Theory. In: Proceedings of the 9th ACM Symposium on Principles of Database Systems; 1990. p. 230–242. doi:10.1145/298514.298576.
• [8] Horwitz S, Reps TW, Binkley D. Interprocedural Slicing Using Dependence Graphs. ACM Transactions on Programming Languages and Systems. 1990;12(1):26–60. Available from: http://doi.acm.org/10.1145/77606.77608.
• [9] Barrett CL, Jacob R, Marathe MV. Formal-Language-Constrained Path Problems. SIAM Journal of Computing. 2000;30(3):809–837. Available from: http://dx.doi.org/10.1137/S0097539798337716.
• [10] Ullman JD, van Gelder A. Parallel Complexity of Logical Query Programs. Algorithmica. 1988;3:5–42. Available from: http://dx.doi.org/10.1007/BF01762108.
• [11] Arora S, Barak B. Computational Complexity: A Modern Approach. Cambridge University Press; 2009. Available from: http://books.google.co.in/books?id=nGvI7cOuOOQC.
• [12] Hopcroft JE, Motwani R, Ullman JD. Introduction to automata theory, languages, and computation – international edition (2. ed). Addison-Wesley; 2003.
• [13] Sudborough IH. On the Tape Complexity of Deterministic Context-Free Languages. Journal of the ACM. 1978;25(3):405–414. Available from: http://doi.acm.org/10.1145/322077.322083.
• [14] Sudborough IH. A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages. Journal of the ACM. 1975;22(4):499–500. Available from: http://doi.acm.org/10.1145/321906.321913.
• [15] Hartmanis J, Immerman N, Mahaney SR. One-Way Log-Tape Reductions. In: Proceedings of 19th Annual Symposium on Foundations of Computer Science; 1978. p. 65–72. doi:10.1109/SFCS.1978.31.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).