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