Komplexitätstheorie
Die Komplexitätstheorie klassifiziert Probleme nach dem Zeit-, Speicher- und sonstigen Ressourcenaufwand, den ein Algorithmus zu ihrer Lösung benötigt, und zieht scharfe Grenzen zwischen effizient lösbaren und scheinbar unlösbaren Problemen.
Definition
Die Komplexitätstheorie untersucht die intrinsische Schwierigkeit von Berechnungsproblemen, gemessen an den Ressourcen, hauptsächlich Laufzeit und Speicher, die zu ihrer Lösung auf einem Modell wie der Turingmaschine erforderlich sind, und gruppiert Probleme entsprechend in Komplexitätsklassen.
Scope
Dieser Bereich umfasst Zeit- und Raumkomplexitätsklassen wie P, NP, PSPACE und die polynomiale Hierarchie, die Theorie der NP-Vollständigkeit und polynomialzeitlichen Reduktionen, die zentrale P-versus-NP-Frage sowie ressourcenbeschränkte Modelle, die Zufälligkeit, Interaktion und Beweise einbeziehen, zusammen mit den Hierarchie- und Härteergebnissen, die diese Klassen miteinander in Beziehung setzen.
Sub-topics
Core questions
- Wie viel Zeit und Speicher benötigt die Lösung eines gegebenen Problems von Natur aus?
- Welche Probleme können effizient gelöst werden und welche scheinen allen effizienten Algorithmen zu widerstehen?
- Wie wird gezeigt, dass Probleme so schwer sind wie die schwierigsten Mitglieder einer Komplexitätsklasse?
- Fügen Zufälligkeit, Interaktion oder Nichtdeterminismus echte Rechenleistung hinzu?
Key theories
- Zeit- und Raumhierarchiesätze
- Mit strikt mehr Zeit oder Raum können Maschinen strikt mehr Probleme lösen, was beweist, dass Komplexitätsklassen echte Hierarchien bilden und dass einige Probleme von Natur aus schwieriger sind als andere.
- NP-Vollständigkeit
- Der Satz von Cook-Levin identifiziert Probleme in NP, auf die sich jedes andere NP-Problem reduzieren lässt, sodass ein einziger effizienter Algorithmus für eines von ihnen alle effizient lösen würde.
- Ressourcenbeschränkte Modelle
- Das Hinzufügen von Zufälligkeit, Interaktion oder Alternation definiert Klassen wie BPP, IP und die polynomiale Hierarchie, deren Beziehungen das Bild schärfen, was zusätzliche Ressourcen leisten können und was nicht.
Clinical relevance
Die Komplexitätstheorie leitet die Praxis, indem sie zertifiziert, welche Probleme effiziente Algorithmen zulassen und welche NP-schwer sind und daher am besten mit Heuristiken oder Approximationen angegangen werden; die angenommene Härte bestimmter Probleme untermauert auch die moderne Kryptographie, deren Sicherheit auf Aufgaben beruht, die als rechnerisch undurchführbar gelten.
History
Hartmanis und Stearns begründeten das Feld 1965, indem sie Komplexitätsklassen definierten und Hierarchiesätze bewiesen. Cook und Levin führten um 1971 die NP-Vollständigkeit ein, Karp zeigte 1972, dass viele natürliche Probleme vollständig sind, und die folgenden Jahrzehnte fügten randomisierte, interaktive und probabilistisch überprüfbare Beweismodelle hinzu.
Key figures
- Stephen Cook
- Richard Karp
- Leonid Levin
- Juris Hartmanis
Related topics
Seminal works
- cook1971
- hartmanisStearns1965
- aroraBarak2009
Frequently asked questions
- Was ist der Unterschied zwischen Berechenbarkeit und Komplexität?
- Die Berechenbarkeit fragt, ob ein Problem überhaupt von einem Algorithmus gelöst werden kann, ungeachtet der Kosten. Die Komplexität geht davon aus, dass das Problem lösbar ist, und fragt, wie teuer diese Lösung in Bezug auf Zeit und Speicher sein muss, wobei feinere Unterscheidungen zwischen den prinzipiell lösbaren Problemen getroffen werden.
- Warum ist NP-Vollständigkeit in der Praxis wichtig?
- Wenn ein Problem als NP-vollständig erwiesen wird, ist es mit Tausenden anderer Probleme verbunden, für die trotz jahrzehntelanger Bemühungen kein effizienter Algorithmus bekannt ist. Dies signalisiert, dass die Suche nach einem schnellen exakten Algorithmus wahrscheinlich vergeblich ist und dass Approximation, Heuristiken oder Spezialfallmethoden der realistische Weg sind.