LOGCFL

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

[Bearbeiten | Quelltext bearbeiten]

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

Hilfskellermaschinen

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

Die Entscheidungsprobleme, die mit einer alternierenden Turing-Maschinen mit logarithmischem Speicheraufwand und polynomiell beschränkter Baumgröße gelöst werden können.

Boolean circuits

[Bearbeiten | Quelltext 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-Gattern mit einem auf 2 beschränkten Fan-in und OR-Gattern mit beliebig großem Fan-in.

Beziehung zu anderen Komplexitätsklassen

[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]
  • Auswerten von azyklischen Boolean conjunctive queries
  • Homomorphie-Problem: Gibt es einen Homomorphismus zwischen zwei azyklischen relationalen Schemata?
  • Ivan H. Sudburough: On the Tape Complexity of Context Free Languages. Journal of the ACM 25(3), pp405,414, 1978.
  • LOGCFL. In: Complexity Zoo. (englisch)