Polynomialzeit

Polynomialzeit, in der Komplexitätstheorie diejenige zur Lösung eines Problems benötigte Rechenzeit, die mit einer Polynomialfunktion, aber nicht stärker wächst. Probleme, für die eine Polynomialzeit existiert, besitzen polynomiale Komplexität und können deterministisch gelöst werden, andere Probleme sind nur heuristisch oder gar nicht lösbar.