Komplexitätstheorie
Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Berechenbarkeit und dem Ressourcenverbrauch (hauptsächlich Ausführungsgeschwindigkeit und Speicherplatzbedarfplatzbedarf) 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,
- nichtdeterministische Maschinen (siehe auch Nichtdeterminismus),
- randomisierte nichtdeterministische Maschinen und
- quantenmechanische Maschinen
- Registermaschinen oder
- spezielle Turingmaschinen
Die Einteilung von algorithmischen Problemen in Komplexitätsklassen erfolgt in
Ein wichtiger Anwendungsbereich der Komplexitätstheorie ist die Kryptographie.Siehe auch: P/NP-Problem, NP (Komplexitätsklasse)