L (Komplexitätsklasse)
eine Komplexitätsklasse (logarithmischen Platzverbrauch)
From Wikipedia, the free encyclopedia
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
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.