„L (Komplexitätsklasse)“ – Versionsunterschied
| [gesichtete Version] | [gesichtete Version] |
K kf |
→Bekannte Probleme in L: + planarität und Verweise auf compendia |
||
| Zeile 15: | Zeile 15: | ||
==Bekannte Probleme in L== |
==Bekannte Probleme in L== |
||
* [[Erreichbarkeitsproblem in Graphen|Erreichbarkeitsproblem in ungerichteten Graphen]] |
* [[Erreichbarkeitsproblem in Graphen|Erreichbarkeitsproblem in ungerichteten Graphen]] |
||
* [[Planarer Graph|Planarität]] von Graphen <ref>{{Literatur| Autor=Eric Allender, Meena Mahajan| Hrsg=H. Reichel, S. Tison| Titel=The Complexity of Planarity Testing| Sammelwerk=STACS 2000| Verlag=Springer | Ort=Berlin, Heidelberg| Datum=2000| Reihe=Lecture Notes in Computer Science| BandReihe=1770| Seiten=87-98| ISBN=978-3-540-67141-1| DOI=10.1007/3-540-46541-3_7}}</ref>, d.h. zu Entscheiden ob ein gegebener Graph planar ist. |
|||
Eine Vielzahl an Problem in L wird in dem Artikel von Cook und McKenzie <ref>{{Literatur |Autor=Stephen A. Cook, Pierre McKenzie |Titel=Problems complete for deterministic logarithmic space |Sammelwerk=Journal of Algorithms |Band=8 |Nummer=3 |Datum=1987 |Seiten=385-394 |DOI=10.1016/0196-6774(87)90018-6}}</ref> und dem Compendium von Alvarez und Greenlaw gelistet<ref>{{Literatur | Autor=C. Alvarez, R. Greenlaw |Titel=A compendium of problems complete for symmetric logarithmic space |Sammelwerk=computational complexity |Band=9 |Nummer=2 |Datum=2000 |Seiten=123–145 |DOI=10.1007/PL00001603}}</ref>. |
|||
==Literatur== |
==Literatur== |
||
Version vom 7. Dezember 2018, 17:43 Uhr
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:
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 Problem in 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.
Weblinks
- ↑ 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.