LOGCFL (Komplexitätsklasse)
aus Wikipedia, der freien Enzyklopädie
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.
Inhaltsverzeichnis |
[Bearbeiten] verschiedene Charakterisierungen
Neben der eigentlichen Definition gibt es noch einige äquivalente Charakterisierungen der Klasse LOGCFL:
[Bearbeiten] 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)
[Bearbeiten] 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.
[Bearbeiten] 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.
[Bearbeiten] 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.
[Bearbeiten] Probleme in LOGCFL
- Auswerten von azyklischen Boolean conjunctive queries
- Homomorphie-Problem: Gibt es einen Homomorphismus zwischen zwei azyklischen relationalen Schemata.
[Bearbeiten] Literatur
Ivan H. Sudburough: On the Tape Complexity of Context Free Languages. Journal of the ACM 25(3), pp405,414, 1978.
[Bearbeiten] Weblinks
- LOGCFL im Complexity Zoo (englisch)