L (Komplexitätsklasse)

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, dass 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.

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

Bekannte Probleme in L

Erreichbarkeitsproblem in ungerichteten Graphen
Planarität von Graphen^[1], d. h. zu Entscheiden ob ein gegebener Graph planar ist.

Eine Vielzahl an Problemen in der Klasse L wird in dem Artikel von Cook und McKenzie^[2] und dem Compendium von Alvarez und Greenlaw gelistet^[3].

Literatur

Omer Reingold. Undirected ST-connectivity in Log-Space. Electronic Colloquium on Computational Complexity. No. 94, 2004.
Stephen A. Cook, Pierre McKenzie: Problems complete for deterministic logarithmic space. In: Journal of Algorithms. Band 8, Nr. 3, 1987, S. 385–394, doi:10.1016/0196-6774(87)90018-6.
C. Alvarez, R. Greenlaw: A compendium of problems complete for symmetric logarithmic space. In: computational complexity. Band 9, Nr. 2, 2000, S. 123–145, doi:10.1007/PL00001603.

Einzelnachweise

↑ Eric Allender, Meena Mahajan: The Complexity of Planarity Testing. In: H. Reichel, S. Tison (Hrsg.): STACS 2000 (= Lecture Notes in Computer Science. Band 1770). Springer, Berlin, Heidelberg 2000, ISBN 978-3-540-67141-1, S. 87–98, doi:10.1007/3-540-46541-3_7.
↑ Stephen A. Cook, Pierre McKenzie: Problems complete for deterministic logarithmic space. In: Journal of Algorithms. Band 8, Nr. 3, 1987, S. 385–394, doi:10.1016/0196-6774(87)90018-6.
↑ C. Alvarez, R. Greenlaw: A compendium of problems complete for symmetric logarithmic space. In: computational complexity. Band 9, Nr. 2, 2000, S. 123–145, doi:10.1007/PL00001603.

Weblinks

L. In: Complexity Zoo. (englisch)
SL. In: Complexity Zoo. (englisch)

[1] Eric Allender, Meena Mahajan: The Complexity of Planarity Testing. In: H. Reichel, S. Tison (Hrsg.): STACS 2000 (= Lecture Notes in Computer Science. Band 1770). Springer, Berlin, Heidelberg 2000, ISBN 978-3-540-67141-1, S. 87–98, doi:10.1007/3-540-46541-3_7.

[2] Stephen A. Cook, Pierre McKenzie: Problems complete for deterministic logarithmic space. In: Journal of Algorithms. Band 8, Nr. 3, 1987, S. 385–394, doi:10.1016/0196-6774(87)90018-6.

[3] C. Alvarez, R. Greenlaw: A compendium of problems complete for symmetric logarithmic space. In: computational complexity. Band 9, Nr. 2, 2000, S. 123–145, doi:10.1007/PL00001603.

[1]

[2]

[3]