LOGCFL (Komplexitätsklasse)
In der Komplexitätstheorie bezeichnet LOGCFL die Komplexitätsklasse der Entscheidungsprobleme die mit logarithmischen 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 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.
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)