LOGCFL (Komplexitätsklasse)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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

Hilfskellermaschinen[Bearbeiten]

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[Bearbeiten]

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

Boolean circuits[Bearbeiten]

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[Bearbeiten]

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.

AC0NC1LNLLOGCFL ⊆ AC1NC2P

Probleme in LOGCFL[Bearbeiten]

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

Literatur[Bearbeiten]

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

Weblinks[Bearbeiten]

  • LOGCFL. In: Complexity Zoo. (englisch)