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 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:

See also

References

  1. ^ 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
  2. ^ 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. ^ 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
  4. ^ 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.