LOGCFL

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 AC¹, 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]

References

^ ^1.0 ^1.1 ^1.2 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
^ ^3.0 ^3.1 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

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.