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.

Formale Definition

Ein Problem wird in polynomieller Zeit lösbar genannt, wenn es dafür einen Lösungsalgorithmus gibt, dessen benötigte Rechenzeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t(n)} (z. B. gemessen als Anzahl der Arbeitsschritte einer Turing-Maschine) höchstens polynomiell mit der Größe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} des Problems (gemessen als Länge der Eingabe für den Lösungsalgorithmus) wächst, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t(n)} die maximale Rechenzeit ist, die der Algorithmus für eine Probleminstanz der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} benötigt. Es existiert ein Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} , das die Rechenzeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t(n)} nach oben beschränkt: für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} ist $p(n)\geq t(n)$. Anders gesagt: Es gibt eine natürliche Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t \in \hbox{O}(n^k)} gemäß der Landau-Notation. Ein solcher Algorithmus heißt Polynomialzeit-Algorithmus oder polynomieller Algorithmus für das Problem.

Beispiel: Polynomieller Algorithmus

Ein einfaches Verfahren zum Sortieren eines Arrays ist das fortwährende Finden und nach hinten Schieben des größten der noch unsortierten Elemente (Selectionsort). Der Aufwand dieses Verfahrens ist quadratisch, weil für jedes Element der Eingabe maximal alle anderen Elemente einmal betrachtet werden müssen. Dadurch ergeben sich n+(n-1)+(n-2)... Vergleiche, deren Summe nach dem kleinen Gauß quadratisch in Abhängigkeit von n wächst. Da eine quadratische Abhängigkeit von der Eingabe polynomiell ist, handelt es sich um einen polynomiellen Algorithmus.

Superpolynomialzeit

Probleme, deren Berechnungszeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t(n)} mit der Problemgröße Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} stärker als mit einer Polynomfunktion wächst, heißen in Superpolynomialzeit lösbar; ein Beispiel dafür ist exponentielle Zeit, also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t \in \Omega(c^n)} mit konstantem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c>1} .

Bezug zu den Komplexitätsklassen

Die Klasse aller Probleme, die sich auf einer deterministischen sequentiellen Maschine in Polynomialzeit lösen lassen, wird als P (von polynomial) bezeichnet. Die Klasse aller Probleme, die sich von einer nichtdeterministischen Maschine in Polynomialzeit lösen lassen, wird als NP (von nondeterministic-polynomial time) bezeichnet. Es ist klar, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P \subseteq NP } , also P eine Teilmenge von NP ist. Eine bis heute unbewiesene Vermutung ist, dass beide Klassen echt verschieden sind, dass also $P\subsetneq NP$ gilt. Das P-NP-Problem gilt als wichtigstes offenes Problem der theoretischen Informatik.

Kritik

Die Polynomialzeit galt bereits in den 1970er Jahren als Grenze zwischen praktisch lösbaren und praktisch unlösbaren Problemen. Diese Abgrenzung ist allerdings für die Praxis nicht trennscharf. Einerseits gibt es auch Methoden mit exponentieller worst-case-Laufzeit, die in der Praxis einsetzbar sind; ein Beispiel hierfür ist der Simplex-Algorithmus. Andererseits wachsen Polynome höheren Grades bereits so schnell, dass viele in Polynomialzeit ablaufende Algorithmen für praktisch vorhandene Problemgrößen dennoch nicht mehr handhabbar sind.

Es spricht jedoch eine Reihe von Gründen für die Beibehaltung der Polynomialzeit als „Grenze der Machbarkeit“. Insbesondere gibt es viele Probleme, für die zunächst nur ein hochgradig polynomielles Verfahren bekannt war (dessen Laufzeit durch ein Polynom hohen Grades begrenzt ist), die aber später auch mit niedrigem polynomiellem Aufwand (etwa vom Grad 2 oder 3) gelöst werden konnten.

Siehe auch

• Pseudopolynomiell