Komplexitätstheorie

Komplexitätstheorie, Teilgebiet der Mathematik beziehungsweise der theoretischen Informatik, das sich mit dem Rechenaufwand (der Komplexität) von Algorithmen beschäftigt. Hauptziel ist es, zu einem Problem den Algorithmus mit dem geringsten Rechenaufwand zu ermitteln. Die Komplexitätstheorie ist damit insbesondere für die Informatik von Bedeutung, da Computer prinzipiell nur zur Lösung