L (Komplexitätsklasse)

aus Wikipedia, der freien Enzyklopädie

In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, welche von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können. Um logarithmischen Platzverbrauch definieren zu können, muss hierbei vorausgesetzt werden, das die Eingabe für das Entscheidungsproblem auf einem separaten Eingabeband gegeben ist. Dieses kann nur gelesen werden und wird für die Angabe des Platzverbrauchs nicht berücksichtigt.

Inhaltsverzeichnis 1 Beziehung zu anderen Komplexitätsklassen 2 SL 3 Bekannte Probleme in L 4 Literatur 5 Weblinks

[Bearbeiten] Beziehung zu anderen Komplexitätsklassen

Die folgenden Beziehungen sind bekannt:

L ⊆ NL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE

Nach dem Platzhierarchiesatz muss mindestens eine dieser Inklusionen echt sein, da L eine echte Teilmenge von PSPACE ist. Bisher ist aber unbekannt, welche dies ist, und ob beispielsweise L=NL oder auch L=P gilt.

[Bearbeiten] SL

Die Klasse SL (engl. für symmetric log-space) ist ursprünglich über das Konzept der symmetrischen Turingmaschine definiert worden. Eine alternative -- und häufiger verwendete -- Charakterisierung definiert dagegen SL als die Klasse aller durch LOGSPACE-Reduktion auf das Problem USTCON reduzierbaren Probleme. Diese Klasse liegt zwischen L und NL, es gilt also

L ⊆ SL ⊆ NL.

Im Jahr 2004 zeigte Omer Reingold allerdings, dass sich USTCON auch mit logarithmischem Platzbedarf lösen lässt. Damit gilt die Gleichheit L=SL.

[Bearbeiten] Bekannte Probleme in L

• Erreichbarkeitsproblem in Graphen

[Bearbeiten] Literatur

• Omer Reingold. Undirected ST-connectivity in Log-Space. Electronic Colloquium on Computational Complexity. No. 94, 2004.

[Bearbeiten] Weblinks

• L im Complexity Zoo (englisch)
• SL im Complexity Zoo (englisch)