Zeit- und Raumkomplexitätsklassen

Komplexitätsklassen gruppieren Entscheidungsprobleme nach dem Zeit- oder Speicherbedarf einer Maschine zu ihrer Lösung und organisieren die Berechnung in einer strukturierten Landschaft von logarithmischem Speicher bis hin zu exponentieller Zeit.

Definition

Eine Komplexitätsklasse ist die Menge von Problemen, die innerhalb einer angegebenen Ressourcengrenze lösbar sind, typischerweise die Zeit oder der Arbeitsspeicher, die von einer Turingmaschine als Funktion der Eingabelänge verwendet werden, mit deterministischen und nichtdeterministischen Varianten für jede Ressource.

Scope

Dieses Thema behandelt die Definition deterministischer und nichtdeterministischer Zeit- und Raumklassen wie P, NP, L, NL, PSPACE und EXPTIME, die Hierarchiesätze, die sie trennen, Inklusionen und bekannte Beziehungen zwischen ihnen, Savitchs Theorem, das nichtdeterministischen und deterministischen Raum in Beziehung setzt, und die vollständigen Probleme, die jede Klasse charakterisieren.

Core questions

• Wie werden Probleme nach dem Zeit- und Speicherbedarf ihrer Lösung gruppiert?
• Welche Inklusionen zwischen den Standard-Komplexitätsklassen sind als strikt bekannt?
• Wie verhält sich nichtdeterministischer Raum zu deterministischem Raum?
• Welche Rolle spielen vollständige Probleme bei der Charakterisierung einer Klasse?

Key theories

Hierarchiesätze

Mit asymptotisch mehr Zeit oder Raum kann eine Maschine strikt mehr Sprachen entscheiden, sodass die Zeit- und Raumklassen echte Hierarchien bilden und Ressourcen nicht verschwendet werden können, ohne Probleme zu verlieren.

Savitchs Theorem

Jedes Problem, das in nichtdeterministischem Raum lösbar ist, kann deterministisch unter Verwendung nur des Quadrats dieses Raums gelöst werden, sodass für den Speicher, im Gegensatz zu scheinbar für die Zeit, Nichtdeterminismus höchstens einen bescheidenen Vorteil bietet.

Clinical relevance

Die Einordnung eines Problems in eine Komplexitätsklasse gibt Praktikern Aufschluss darüber, was zu erwarten ist: Probleme in P skalieren auf große Eingaben, PSPACE-vollständige Probleme wie viele Spiele und Planungsaufgaben widerstehen einer effizienten Lösung, und die Klassenstruktur leitet an, ob exakte Algorithmen, Approximationen oder eine Neugestaltung des Problems angestrebt werden sollten.

History

Hartmanis und Stearns definierten 1965 zeitbeschränkte Klassen und bewiesen den Zeithierarchiesatz, womit sie das Feld begründeten. Die Raumkomplexität wurde parallel dazu entwickelt, wobei Savitchs Theorem von 1970 und spätere Ergebnisse wie die Abschließung des nichtdeterministischen Raums unter Komplement durch Immerman und Szelepcsényi das Bild verfeinerten.

Key figures

• Juris Hartmanis
• Richard Stearns
• Walter Savitch
• Stephen Cook

Seminal works

• hartmanisStearns1965
• savitch1970

Frequently asked questions

Was ist der Unterschied zwischen Zeit- und Raumkomplexität?

Die Zeitkomplexität zählt die Anzahl der Schritte, die ein Algorithmus benötigt, während die Raumkomplexität den von ihm verwendeten Arbeitsspeicher misst. Sie verhalten sich unterschiedlich: Speicher kann während einer Berechnung wiederverwendet werden, weshalb nichtdeterministischer Raum im Vergleich zu deterministischem Raum weitaus weniger mächtig ist, als der analoge Vergleich für die Zeit zu sein scheint.

Warum sind Hierarchiesätze wichtig?

Sie beweisen, dass mehr Ressourcen tatsächlich die Lösung von mehr Problemen ermöglichen und schließen die Möglichkeit aus, dass alle Klassen in einer zusammenfallen. Dies garantiert zum Beispiel, dass es Probleme gibt, die in exponentieller Zeit, aber nicht in polynomialer Zeit lösbar sind, was das gesamte Gebäude der Komplexitätsklassen verankert.