Komplexitätstheorie
Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befaßt sich mit der Ausführungsgeschwindigkeit von Algorithmen, deren Speicherverbrauch sowie der Optimierung derselben in Abhängigkeit der Mächtigkeit der Eingabedaten.
Die Komplexitätstheorie versucht zu ermitteln, ob ein bestimmter Algorithmus für einen gegebenen Zweck hinsichtlich Zeitaufwand geeignet ist. Dabei werden die Algorithmen in bestimmte Komplexitätsklassen eingeteilt wie 'linear', 'logarithmisch', 'polynomiell', 'nichtdeterministisch - polynomiell' usw.
Ein wichtiger Anwendungsbereich der Komplexitätstheorie ist die Kryptographie.