Back Temps polinòmic Catalan Polynomiel tid Danish Time complexity#Polynomial time English Polinoma tempo Esperanto Tiempo polinómico Spanish 多項式時間 Japanese 다항 시간 Korean Polynomiale tijd Dutch Algorytm wielomianowy Polish Complexidade de tempo Portuguese
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.[1]
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.
- ↑ Computing exponentially faster using DNA. In: next BIG Future. 1. März 2017, abgerufen am 10. März 2017 (englisch).