L (Komplexitätsklasse)
In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können.
| Inhaltsverzeichnis |
Beziehung zu anderen Komplexitätsklassen
Die folgenden Beziehungen sind bekannt:
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
- L im Complexity Zoo (englisch)
- SL im Complexity Zoo (englisch)