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:

LOGCFL is the set of decision problems solvable by nondeterministic auxiliary pushdown automata in log space and polynomial time.[5]

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
  5. ^ 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.
P ≟ NP 

This theoretical computer science–related article is a stub. You can help Wikipedia by adding missing information.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.