In computational complexity theory, LOGCFL is the complexity class that contains all decision problems that can be reduced in logarithmic space to a context-free language.[1] This class is closed under complementation.[1] It is situated between NL and AC1, in the sense that it contains the former[1] and is contained in the latter.[2] Problems that are complete for LOGCFL include many problems that can be characterized by acyclic hypergraphs:
- evaluating acyclic Boolean conjunctive queries[3]
- checking the existence of a homomorphism between two acyclic relational structures[4]
- checking the existence of solutions of acyclic constraint satisfaction problems[3]
LOGCFL is the set of decision problems solvable by nondeterministic auxiliary pushdown automata in log space and polynomial time.[5]
See also
editReferences
edit- ^ a b c Hemaspaandra, Lane A.; Ogihara, Mitsunori (2002), The Complexity Theory Companion, Texts in Theoretical Computer Science: An EATCS Series, Springer, p. 280, doi:10.1007/978-3-662-04880-1, ISBN 9783662048801
- ^ Kapron, Bruce M., ed. (2023), Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook, ACM Books, Morgan & Claypool, p. 124, ISBN 9798400707803
- ^ a b Gottlob, Georg; Leone, Nicola; Scarcello, Francesco (2001), "The complexity of acyclic conjunctive queries", Journal of the ACM, 48 (3): 431–498, doi:10.1145/382780.382783
- ^ Vortmeier, Nils; Kokkinis, Ioannis (2021), "The dynamic complexity of acyclic hypergraph homomorphisms", in Kowalik, Lukasz; Pilipczuk, Michal; Rzazewski, Pawel (eds.), Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Warsaw, Poland, June 23-25, 2021, Revised Selected Papers, Lecture Notes in Computer Science, vol. 12911, Springer, pp. 232–244, arXiv:2107.06121, doi:10.1007/978-3-030-86838-3_18, ISBN 978-3-030-86837-6
- ^ Sudborough, I. H. (July 1978). "On the Tape Complexity of Deterministic Context-Free Languages". Journal of the ACM. 25 (3): 405–414. doi:10.1145/322077.322083. ISSN 0004-5411.
