Komplexitätsklasse

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 Komplexitätsklasse durch eine obere Schranke für den Bedarf einer bestimmten Ressource unter Voraussetzung eines Berechnungsmodells. Die am häufigsten betrachteten Ressourcen sind die Anzahl der notwendigen Berechnungsschritte zur Lösung eines Problems (Zeitkomplexität) oder der Bedarf an Speicherplatz (Raum- oder Platzkomplexität). Gemessen wird der Ressourcenbedarf in der Regel durch sein asymptotisches Verhalten an der Obergrenze (dem worst case) in Abhängigkeit von der Länge der Eingabe (Problemgröße).

Auch andere Maße des Ressourcenbedarfs sind möglich, etwa der statistische Mittelwert über alle möglichen Eingaben. Dieses Maß ist jedoch formal nur schwer zu analysieren.

Da durch eine Komplexitätsklasse nur eine obere Grenze für den Ressourcenbedarf festgelegt ist, wird somit für ein gegebenes Berechnungsmodell eine Hierarchie von Komplexitätsklassen gebildet, wobei weniger mächtige Klassen jeweils vollständig in den jeweils höheren Komplexitätsklassen enthalten sind. Zudem können durch formale Methoden auch über unterschiedliche Berechnungsmodelle oder Ressourcen definierte Klassen zueinander in Bezug gesetzt werden.

Inhaltsverzeichnis

Einteilung der Komplexitätsklassen

Die Komplexität wird häufig mit Hilfe der Landau-Symbole beschrieben, um von Eigenheiten bestimmter Implementierungen und Berechnungsmodelle zu abstrahieren. Die Schwierigkeit bei der Bestimmung der genauen Komplexität eines Problems liegt darin, dass man hierfür sämtliche möglichen Algorithmen für dieses Problem betrachten müsste. Man muss also beweisen, dass ein bestimmter Algorithmus optimal für dieses Problem ist.

Die Komplexitätsklasse eines Algorithmus ist nur in einer konkreten Implementierung auf einer Maschine, z. B. auf einer Turingmaschine oder im Lambda-Kalkül feststellbar. Die Komplexitätsklassen der Implementationen eines Algorithmus auf unterschiedlichen Maschinenmodellen sind jedoch meistens ähnlich oder sogar - je nach Abstraktionslevel - gleich.

Es wird festgestellt, dass nur bestimmte Klassen dieser Größe sinnvoll unterscheidbar sind, die alle mit einer charakteristischen Gleichung beschrieben werden. So interessieren z. B. konstante Faktoren in der Komplexität eines Algorithmus nicht - schließlich gibt es in der Realität (Computer) auch Maschinen, deren Ausführungsgeschwindigkeit sich um einen konstanten Faktor unterscheidet. Hier wird auch klar, warum keine Einheiten gebraucht werden und wie die Landau-Notation zu verstehen ist.

Eine wichtige Rolle bei der Einteilung der Komplexitätsklassen spielt die Unterscheidung von Zeitkomplexität und Platzkomplexität, bei deren Betrachtung Zeit bzw. Platz beschränkt werden. Weiterhin unterscheidet man deterministische Maschinen von nichtdeterministischen. Informell lässt sich sagen, dass Platz mächtiger ist als Zeit und Nichtdeterminismus meistens mächtiger als Determinismus, allerdings jeweils nur exponentiell mächtiger. Genauere Abschätzungen hierzu geben der Satz von Savitch und der Satz von Immerman und Szelepcsényi.

Ein Problem A, das mit geringem Aufwand auf ein Problem B zurückgeführt (reduziert) werden kann, gehört mindestens zur Komplexitätsklasse von B. B wird dann schwerer als A genannt. Ein Problem A ist K-schwer, wenn sich alle anderen Probleme der Klasse K auf A zurückführen lassen. Liegt ein K-schweres Problem A selbst in der Klasse K, wird es K-vollständig genannt.[1]

Beispiel

Rasenmähen hat mindestens lineare Komplexität (in der Fläche), denn man muss die gesamte Fläche mindestens einmal überfahren. Suchen im Telefonbuch hat hingegen nur logarithmische Komplexität, denn bei doppelt so dickem Telefonbuch schlägt man dieses nur einmal öfter auf, z. B. genau in der Mitte – dann hat man das Problem auf die Hälfte reduziert – siehe binäre Suche.

Siehe auch

Einzelnachweise

  1. siehe auch: Kliewer, Natalia: Komplexitätstheorie, in: Lexikon der Wirtschaftsinformatik, Online-Lexikon, Oldenbourg Wissenschaftsverlag

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

  • 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

  • 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… …   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”