Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Berechenbarkeit und dem Ressourcenverbrauch (hauptsächlich Ausführungsgeschwindigkeit und Speicherplatzbedarf) von Algorithmen auf verschiedenen mathematisch definierten formalen Rechnermodellen, sowie der Güte derartiger Algorithmen. Kostenmaße spielen eine wichtige Rolle.
Als Rechnermodelltypen werden dabei hauptsächlich
- deterministische Maschinen,
- randomisierte Maschinen,
- nichtdeterministische Maschinen,
- randomisierte nichtdeterministische Maschinen und
- quantenmechanische Maschinen
untersucht. In der Regel werden diese als
- Registermaschinen oder
- spezielle Turingmaschinen
realisiert.
Die Einteilung von algorithmischen Problemen in Komplexitätsklassen erfolgt in
Ein wichtiger Anwendungsbereich der Komplexitätstheorie ist die Kryptographie.
Das P/NP-Problem
Aufgabe ist es nun, nicht nur die Algorithmen zu klassifizieren, sondern auch die Lösbarkeit von algorithmischen Problemen zu bestimmen. Die zentrale Fragestellung der Komplexitätstheorie ist derzeit die Äquivalenz der Komplexitätsklassen P und NP. Diese beschränken die Ressource Zeit für deterministische (P) bzw. nichtdeterministische (NP) Maschinen polynomiell in Abhängigkeit der Eingabelänge. Es wird allgemein angenommen, dass P≠NP gilt. Die Annahme wird damit begründet, dass es spezielle algorithmische Probleme gibt, die NP-vollständig sind. Kann man für eines dieser Probleme zeigen, dass es in P liegt, so folgt die Äquivalenz von P und NP. Da einige der Probleme aber schon seit mehreren 1000 Jahren bekannt sind, bisher aber noch niemand einen polynomiellen Algorithmus gefunden hat, geht man von Ungleichheit aus.
Bisher ist eine Separierung der beiden Klassen aber noch nicht gelungen, und P≠NP daher noch nicht bewiesen. Die Schwierigkeit beruht generell darin, für algorithmische Probleme untere Schranken für ihre Komplexität anzugeben. Obere Schranken findet man leicht durch Angabe eines Algorithmus, der die entsprechenden Eigenschaften besitzt. Für untere Schranken ist es jedoch nötig zu beweisen, dass kein Algorithmus mit den gewünschten Eigenschaften existiert. Bisher sind kaum Methoden und Verfahren bekannt, um untere Schranken zu beweisen.
Siehe auch: NP (Komplexitätsklasse)