LOGCFL (Komplexitätsklasse)

In der Komplexitätstheorie bezeichnet LOGCFL die Komplexitätsklasse der Entscheidungsprobleme die mit logarithmischen Speicheraufwand auf eine kontextfreie Sprache (engl. Context-Free Language) reduziert werden können.

verschiedene Charakterisierungen

Neben der eigentlichen Definition gibt es noch einige äquivalente Charakterisierungen der Klasse LOGCFL:

Hilfskellermaschinen

Die Entscheidungsprobleme die eine nichtdeterministische Hilfskellermaschine mit logarithmisch platzbeschränktem Arbeitsband, einem Kellerspeicher und polynomiell beschränkter Laufzeit lösen kann. (von Ivan H.Sudborough)

Alternierende Turing Maschinen

Die Entscheidungsprobleme die mit einer Alternierenden Turing Maschinen mit logarithmischen Speicheraufwand und polynomiell beschränkter Baumgröße gelöst werden können.

Boolean circuits

Die Entscheidungsprobleme die durch Familien von "semi-unbounded Boolean circuits" mit einer durch O(log n) beschränkten Tiefe gelöst werden können. Diese Schaltkreise bestehen aus AND-Gates mit einem auf 2 beschränkten FANIN und OR-Gates mit beliebig großen FANIN.

Beziehung zu anderen Komplexitätsklassen

Aus der Definition von LOGCFL folgt, dass alle Sprachen aus LOGCFL in polynomieller Zeit entschieden werden können also LOGCFL ⊆ P. Ob diese Inklusion echt ist, ist ein wesentliches offenes Problem der Komplexitätstheorie. Weiterhin ist bekannt, dass LOGCFL ⊆ NC gilt.

AC⁰ ⊆ NC¹ ⊆ L ⊆ NL ⊆ LOGCFL ⊆ AC¹ ⊆ NC² ⊆ P

Probleme in LOGCFL

• Auswerten von azyklischen Boolean conjunctive queries
• Homomorphie-Problem: Gibt es einen Homomorphismus zwischen zwei azyklischen relationalen Schemata.

Literatur

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

Weblinks

• LOGCFL. In: Complexity Zoo. (englisch)