In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn die benötigte Rechenzeit einer deterministischen, sequentiellen Rechenmaschine mit der Problemgrösse nicht stärker als mit einer Polynomfunktion wächst (Wiki sei dank)
Die besondere Bedeutung der Polynomialzeit besteht darin, dass man sie als eine Grenze zwischen praktisch lösbaren und praktisch nicht lösbaren Problemen betrachtet. Der Aufwand für Probleme, die nicht in Polynomialzeit lösbar sind, wächst im Allgemeinen so schnell, dass schon relativ geringe Problemgrössen mit verfügbaren Rechnern nicht in überschaubaren Zeiträumen gelöst werden können.
Dieser Sachverhalt ist unabhängig vom technologischen Fortschritt, insoweit er die Geschwindigkeit deterministischer Rechner betrifft. Eine Sonderstellung nimmt der Quantencomputer ein, da er bestimmte nichtdeterministische Operationen ermöglicht.
Und übrigens gehören Dinge, wie Liebe, Männer und Frauen, sowie Videorecorder auch zu den Elementen, die sich der Polynomialzeit widersetzen. Euch viel Spass bei allen nicht deterministischen, sequentiellen Aufgaben, die Ihr so zu erledigen habt.