LOGCFL (complexity class)

from Wikipedia, the free encyclopedia

In complexity theory , LOGCFL denotes the complexity class of decision problems that can be reduced to a context-free language using logarithmic memory requirements .

Different characterizations

In addition to the actual definition, there are some equivalent characterizations of the LOGCFL class:

Auxiliary basement machines

The decision-making problems that a nondeterministic auxiliary basement machine with a logarithmically space-restricted working band, a stack and a polynomial-restricted run time can solve. (by Ivan H. Sudborough )

Alternating Turing machines

The decision problems that can be solved with an alternating Turing machine with logarithmic memory requirements and polynomially limited tree size.

Boolean circuits

The decision problems that can be solved by families of "semi-unbounded Boolean circuits" with a depth limited by O (log n). These circuits consist of AND gates with a FANIN limited to 2 and OR gates with a FANIN of any size.

Relationship to other complexity classes

From the definition of LOGCFL it follows that all languages ​​from LOGCFL can be decided in polynomial time, i.e. LOGCFL ⊆ P. Whether this inclusion is real is an essential open problem of complexity theory. It is also known that LOGCFL ⊆ NC applies.

AC 0 ⊆ NC 1 ⊆ L ⊆ NL ⊆ LOGCFL ⊆ AC 1 ⊆ NC 2 ⊆ P

Problems in LOGCFL

  • Evaluation of acyclic Boolean conjunctive queries
  • Homomorphism problem: Is there a homomorphism between two acyclic relational schemes.

literature

  • Ivan H. Sudburough: On the Tape Complexity of Context Free Languages. Journal of the ACM 25 (3), pp405,414, 1978.

Web links

  • LOGCFL . In: Complexity Zoo. (English)