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