SL (Komplexitätsklasse)

SL (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, das 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.

Inhaltsverzeichnis

Beziehung zu anderen Komplexitätsklassen

Die folgenden Beziehungen sind bekannt:

LNLNCPNPPSPACE

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

Literatur

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

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Komplexitätsklasse P — In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, welche die Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der… …   Deutsch Wikipedia

  • Komplexitätsklasse NP — NP (nichtdeterministisch polynomielle Zeit) ist eine Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Sie bezeichnet die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge …   Deutsch Wikipedia

  • Komplexitätsklasse — Zusammenhang verschiedener Komplexitätsklassen Eine Komplexitätsklasse ist in der Komplexitätstheorie eine Kategorie von Problemen beziehungsweise von Algorithmen, zusammengefasst nach einem gemeinsamen Maß der Komplexität. Definiert wird eine… …   Deutsch Wikipedia

  • Co-RP (Komplexitätsklasse) — co RP (random polynominal) bzw. co RP(ε(n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomineller maximaler Rechenzeit gibt, der jede zu akzeptierende Eingabe mit Wahrscheinlichkeit 1… …   Deutsch Wikipedia

  • BQP (Komplexitätsklasse) — Die Komplexitätsklasse BQP (bounded error quantum polynomial time) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. Zu BQP gehören alle Probleme, die auf einem Quantencomputer in Polynomialzeit mit einer …   Deutsch Wikipedia

  • P (Komplexitätsklasse) — In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, welche die Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der… …   Deutsch Wikipedia

  • Co-NP (Komplexitätsklasse) — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. In der Komplexitätstheorie bezeichnet Co NP eine Komplexitätsklasse …   Deutsch Wikipedia

  • PH (Komplexitätsklasse) — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Die Polynomialzeithierarchie (PH, auch: polynomielle Hierarchie)… …   Deutsch Wikipedia

  • NP (Komplexitätsklasse) — NP (nichtdeterministisch polynomielle Zeit) ist in der Informatik eine Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Sie bezeichnet die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine… …   Deutsch Wikipedia

  • RP (Komplexitätsklasse) — RP (random polynomial) bzw. RP( (n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus A mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”