In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn die benötigte Rechenzeit einer deterministischen Rechenmaschine mit der Problemgröße nicht stärker als mit einer Polynomfunktion wächst. Die besondere Bedeutung der Polynomialzeit besteht darin, dass man sie als eine Grenze zwischen praktisch lösbaren ...