LOGCFL
# 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.

    $AC^0$ ⊆ $NC^1$ ⊆ L ⊆ NL ⊆ LOGCFL ⊆ $AC^1$ ⊆ $NC^2$ ⊆ P

## Probleme in LOGCFL

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