Polynomialzeit

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 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ößen 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.