Polynomialzeit
Rechenzeit, die polynomial mit der Problemgröße wächst / aus Wikipedia, der freien encyclopedia
Liebe Wikiwand-AI, fassen wir uns kurz, indem wir einfach diese Schlüsselfragen beantworten:
Können Sie die wichtigsten Fakten und Statistiken dazu auflisten Polynomialzeit?
Fass diesen Artikel für einen 10-Jährigen zusammen
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.