Polynomieller Algorithmus

Polynomieller Algorithmus

In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn die benötigte Rechenzeit einer deterministischen, sequentiellen 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.

Ob ein gegebenes Problem in Polynomialzeit lösbar ist, ist nicht von vornherein klar. So wurde erst 2002 von Agrawal, Kayal und Saxena ein Algorithmus (AKS-Primzahltest) angegeben, der in polynomialer Zeit entscheidet, ob eine vorgegebene natürliche Zahl eine Primzahl ist oder nicht. Das natürliche Verfahren, einfach alle möglichen Teiler durchzuprobieren, ist nicht polynomial.

Inhaltsverzeichnis

Formale Definition

Ein Problem wird in polynomieller Zeit lösbar genannt, wenn es von einem Algorithmus gelöst wird, dessen benötigte Rechenzeit m (z. B. gemessen als Anzahl von Bitoperationen eines passenden Algorithmus auf einer Turing-Maschine) höchstens polynomial mit der Größe der Eingabe n des Problems (z. B. gemessen in Anzahl Bits) wächst, d. h. es gibt eine natürliche konstante Zahl k\geq 1 mit m(n) = O(nk) gemäß der Landau-Notation.

Polynomieller Algorithmus - ein Beispiel

Ein einfaches Verfahren zum Sortieren eines Arrays ist das fortwährende Finden und Löschen des größten der vorhandenen Elemente. Der Aufwand dieses Verfahrens ist quadratisch, weil für jedes Element der Eingabe maximal alle anderen Elemente einmal betrachtet werden müssen. Da eine quadratische Abhängigkeit von der Eingabe auch polynomiell ist, handelt es sich um einen polynomiellen Algorithmus.

Superpolynomialzeit

Probleme, deren Berechnungszeit mit der Problemgröße stärker als mit einer Polynomfunktion wächst, heißen in Superpolynomialzeit lösbar; ein Beispiel dafür ist exponentielle Zeit, also m(n) = Ω(cn) mit c > 1 konstant.

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 (hypothetischen) nichtdeterministischen Maschine in Polynomialzeit lösen lassen, wird als NP (von nondeterministic-polynomial time) bezeichnet. Es ist klar, dass  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 wurde bereits in den 1970er Jahren als Grenze zwischen den praktisch lösbaren und den praktisch unlösbaren Problemen angesehen. 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 hat sich herausgestellt, dass viele Probleme, die lange Zeit nur mit schlechtem (hochgradigem) polynomiellen Aufwand lösbar waren, jeweils recht bald auch mit niedrigem polynomiellem Aufwand (etwa vom Grad 2 oder 3) gelöst werden konnten.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmus von Edmonds und Karp — Der Edmonds Karp Algorithmus ist in der Informatik und der Graphentheorie eine Implementierung der Ford Fulkerson Methode zur Berechnung des maximalen s t Flusses in Netzwerken mit positiven reellen Kapazitäten. Sie verwendet den jeweils… …   Deutsch Wikipedia

  • Polynomialzeit-Algorithmus — In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn die benötigte Rechenzeit einer deterministischen, sequentiellen Rechenmaschine mit der Problemgröße nicht stärker als mit einer Polynomfunktion wächst. Die… …   Deutsch Wikipedia

  • Edmonds-Karp-Algorithmus — Der Edmonds Karp Algorithmus ist in der Informatik und der Graphentheorie eine Implementierung der Ford Fulkerson Methode zur Berechnung des maximalen Flusses in Netzwerken. Sie verwendet den jeweils kürzesten augmentierenden Pfad in jedem… …   Deutsch Wikipedia

  • Clique (Graphentheorie) — Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als… …   Deutsch Wikipedia

  • Cliquenzahl — Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als… …   Deutsch Wikipedia

  • Größte Clique — Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als… …   Deutsch Wikipedia

  • Größte stabile Menge — Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als… …   Deutsch Wikipedia

  • Knotenüberdeckung — Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als… …   Deutsch Wikipedia

  • Maximale Clique — Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als… …   Deutsch Wikipedia

  • Maximale stabile Menge — Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”