Hier wird die Komplexitätstheorie im Sinne der Informatik abgehandelt. Zur Komplexitätstheorie im kybernetischen Sinne finden Sie mehr unter komplexe Systeme

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 (siehe auch Determinismus (Algorithmus)),
• randomisierte Maschinen (die durch randomisierte Algorithmen simuliert werden),
• nichtdeterministische Maschinen (siehe auch Nichtdeterminismus),
• 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

• Zeitkomplexität und
• Platzkomplexität

Ein wichtiger Anwendungsbereich der Komplexitätstheorie ist die Kryptographie.

Siehe auch

P/NP-Problem, NP (Komplexitätsklasse)