LOGCFL

In der Komplexitätstheorie bezeichnet LOGCFL die Komplexitätsklasse der Entscheidungsprobleme, die mit logarithmischem Speicheraufwand auf eine kontextfreie Sprache (englisch 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 logarithmischem 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-Gattern mit einem auf 2 beschränkten Fan-in und OR-Gattern mit beliebig großem Fan-in.

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)