Polynomialzeit

In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn es mit einer deterministischen Rechenmaschine in einer Rechenzeit lösbar ist, die mit der Problemgröße nicht stärker als gemäß einer Polynomfunktion wächst. Die Polynomialzeit gilt als eine Grenze zwischen praktisch lösbaren und praktisch nicht lösbaren Problemen. Der Aufwand für Probleme, die nicht in Polynomialzeit lösbar sind, wächst im Allgemeinen so schnell, dass schon relativ kleine Probleme mit verfügbaren Rechnern nicht in überschaubarer Zeit gelöst werden können. Dieser Sachverhalt ist unabhängig vom technologischen Fortschritt, insoweit er die Geschwindigkeit deterministischer Rechner betrifft. Eine Sonderstellung nehmen Quantencomputer und DNA-Computer ein, da sie bestimmte nichtdeterministische Operationen ermöglichen. Ob ein gegebenes Problem in Polynomialzeit lösbar ist, ist nicht immer von vornherein klar. So wurde für das Problem, zu entscheiden, ob eine gegebene natürliche Zahl eine Primzahl ist, erst 2002 von Agrawal, Kayal und Saxena ein in Polynomialzeit laufender Algorithmus angegeben (AKS-Primzahltest). Das naive Verfahren, alle möglichen Teiler durchzuprobieren, ist nicht in Polynomialzeit durchführbar.