In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können.

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.

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 Log-space 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.

Literatur

---

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

Weblinks

---

Komplexitätstheorie

L (complexity) | L (סיבוכיות)