Polynomialzeit
In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn die Rechenzeit m mit der Problemgröße n nicht stärker als mit einer Polynomischen Funktion wächst.
In mathematischer Schreibweise m(n) = O(nk), wobei k eine Konsante ist.
Probleme deren Berechnungszeit mit der Problemgröße stärker als mit einer Polynomischen Funktion wächst, heißen in Superpolynomialzeit lösbar, ein Beispiel dafür ist Exponentialzeit. Probleme die in Polynomialzeit lösbar sind werden machnmal als schnell lösbar bezeichnet.
Die Klasse aller Probleme, die sich auf einer deterministischen sequentiellen Machine in Polynomialzeit lösen lassen wird als P bezeichnet, die Klasse aller Probleme, die sich nicht in Polynomialzeit lösen lassen als NP.