Jump to content

LOGCFL

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 31.33.164.250 (talk) at 09:36, 5 September 2019. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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. This class is situated between NL and AC¹, in the sense that it contains the former and is contained in the latter. Problems that are complete for LOGCFL include many problems whose instances can be characterized by acyclic hypergraphs:

evaluating acyclic Boolean conjunctive queries
checking the existence of a homomorphism between two acyclic relational structures
checking the existence of solutions of acyclic constraint satisfaction problems

See also

List of complexity classes

External links

Complexity Zoo: LOGCFL

P ≟ NP

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=LOGCFL&oldid=914120701"

Hidden category:

All stub articles