Warum heißt Polynomialzeit „effizient“?

Warum wird in der Informatik jede höchstens polynomielle Komplexität als effizient angesehen?

Für jede praktische Anwendung ^(a) sind Algorithmen mit der Komplexität viel schneller als Algorithmen, die zeitlich ausgeführt werden, beispielsweise , aber die erste wird als ineffizient angesehen, während die letztere effizient ist. Wo ist die Logik ?!$n^{\log n}$$n^{80}$

^{(a) Nehmen wir zum Beispiel an, dass die Anzahl der Atome im Universum ungefähr beträgt .$10^{80}$}

Eine andere Perspektive auf "Effizienz" ist, dass wir mit Hilfe der Polynomzeit einen Begriff von "Effizienz" definieren können, der nicht von Maschinenmodellen abhängt. Insbesondere gibt es eine Variante der Church-Turing-These, die als "effektive Church-Turing-These" bezeichnet wird und besagt, dass jedes Problem, das in Polynomzeit auf einer Art von Maschinenmodell abläuft, auch in Polynomzeit auf einem anderen, ebenso leistungsfähigen Maschinenmodell abläuft.

Dies ist eine schwächere Aussage zur allgemeinen CT-These und wird sowohl von randomisierten Algorithmen als auch von Quantenalgorithmen "irgendwie" verletzt, wurde jedoch nicht in dem Sinne verletzt, dass ein NP-hartes Problem in Polyzeit durch Veränderung gelöst werden kann das Maschinenmodell.

Dies ist letztendlich der Grund, warum die Polynomzeit ein beliebter Begriff in der Theorie CS ist. Die meisten Menschen erkennen jedoch, dass dies nicht die "praktische Effizienz" widerspiegelt. Um mehr darüber zu erfahren, ist Dick Liptons Post über ' galaktische Algorithmen ' eine großartige Lektüre.

Theoretisch kümmern wir uns um das asymptotische Verhalten und beschreiben Klassen von Problemen und Algorithmen auf der Grundlage ihres asymptotischen Verhaltens. Das Schlüsselwort hier ist asymptotisch . ist asymptotisch schneller als , dh beginnend mit (was übrigens heißt: septillion!), Unter der Annahme von Einheitskonstanten und nicht niedrig -Bestellbedingungen.$O(n^{80})$$O(n^{\log n})$$n > 1208925819614629174706176$

In der Praxis wird jedoch sowohl auf Exponenten als auch auf konstante Koeffizienten geachtet. In der Praxis können die Eingabegrößen nicht auf mehrere Millionen anwachsen. Daher ist für alle Zwecke eine bessere Wahl als . Andere Faktoren spielen in der Praxis ebenfalls eine Rolle: Parallelität, Speicherzugriffsmuster (z. B. Lokalität).$n^{\log n}$$n^{80}$

Beispielsweise implementieren die meisten Bibliotheken für die ganzzahlige Multiplikation, z. B. GMP , eine Mischung von Algorithmen und wählen einen minderwertigen Algorithmus basierend auf der Eingabegröße aus. Wählen Sie die praktisch überlegenen Algorithmen basierend auf der Eingabegröße aus, obwohl diese Algorithmen möglicherweise asymptotisch minderwertig sind. Einige asymptotisch "minderwertige" Algorithmen sind bei bestimmten Eingabegrößen schneller und werden über den optimalen Algorithmen ausgewählt.

Ein anderes Beispiel, der schnellste bekannte Matrixmultiplikationsalgorithmus, ist der Coppersmith-Winograd-Algorithmus , der in (es gibt jüngste Verbesserungen; mehr hier ). Es wurde jedoch nie implementiert, weil (1) es schwierig ist (2) der konstante Koeffizient gigantisch ist. Alle linearen Algebra-Pakete verwenden das weniger optimale von Strassen .$O(n^{2.3737})$

Die TL; DR-Theorie berücksichtigt asymptotisches Verhalten, um Algorithmen zu vergleichen, da die Grenze der Eingabegröße auf beliebig große Zahlen beschränkt ist.

Diese Antwort befasst sich mit dem Gesamtzusammenhang Ihrer Frage. Die Informatik ist eigentlich eine relativ junge und etwas offene Wissenschaft und hat noch keine guten Antworten auf einige grundlegende Fragen. Die Grundfrage "Was wird effizient berechnet ?" Wird in CS (je nach Meinung) entweder genau oder grob als das berühmte P vs NP-Problem (oder das eng verwandte P vs Exptime-Problem) formuliert und ist nach mehr als vier Jahrzehnten immer noch offen Anfänglich vorgestellt von Cook / Levin ~ 1970 und intensive Arbeit der weltbesten Informatiker (und viele Mathematiker interessieren sich auch für das Problem als grundlegend).

Mit anderen Worten, selbst mit einer groben Definition von "effizient" als P - Zeit und einer der am höchsten bewerteten wissenschaftlichen Auszeichnungen - nämlich einem mit dem Problem verbundenen Preis von 1 Million US - Dollar für mehr als 10 Jahre - kann die Informatik nicht einmal beweisen, dass einige Probleme (in der Nähe von Diese Grenze muss oder darf keine effizienten (Ptime) Algorithmen haben. Daher ist die genaue Definition von "effizient" genauer als P-Zeit zu diesem Zeitpunkt nicht notwendig oder sogar möglich . Wenn / wenn die P vs NP-Vermutung auf die eine oder andere Weise festgelegt wird, ist möglicherweise oder vermutlich eine genauere Definition von "effizient" möglich.

Darüber hinaus könnte man der Meinung sein, dass die Ptime-Definition von "effizient" sogar ein bisschen "schlampig" sein könnte, und die meisten Informatiker würden dem wahrscheinlich zustimmen, und fast alle halten es für äußerst wichtig, die P vs. NP-Vermutung aufzulösen der Punkt, an dem sie diese Behauptung oder Beobachtung vielleicht sogar als trivial ansehen ... mit anderen Worten, es ist sozusagen ein Work in Progress / wir arbeiten daran . (Tatsächlich gehen die etablierten Informatiker nur halb im Scherz so weit, die Lücke und das Fehlen von Fortschritten / endgültigen Trennungen routinemäßig als peinlich zu bezeichnen .)

Tatsächlich gibt es sogar eine eng verwandte / signifikant stärkere Vermutung als P gegen NP, nämlich NP gegen P / Poly, die derzeit auch von der Informatik nicht gelöst werden kann. es wird vermutet, dass NP-Zeit-Probleme nicht durch "P-große" Schaltungen gelöst werden können , dh nicht einmal auf jene Schaltungen beschränkt sind, die durch Algorithmen / Turing-Maschinen erzeugt werden können.

Wie hart P gegen NP sein mag - es gibt einen soliden Grund zu der Annahme, dass es mindestens so schwer ist wie die sehr alte Riemann-Vermutung in der Mathematik (jetzt 1,5 Jahrhundert alt), da beide den gleichen Preis von 1 Million US-Dollar für mehr als ein Jahrzehnt, und keiner wurde noch / zuerst gelöst.

Mit anderen Worten, genau zu definieren, welche Algorithmen wirklich "effizient" sind, ist eines der wichtigsten und schwierigsten offenen Probleme in der theoretischen Wissenschaft und Mathematik .

Tatsächlich ist die Frage "Was wird effizient berechnet?" Sogar noch subtiler, da es eine Variante der Church-Turing-These gibt, die als P-Zeit-CT-These bezeichnet wird, und nicht bekannt ist, ob das Quantencomputing tatsächlich dagegen verstößt . Mit Shors bahnbrechendem Ergebnis der P-Zeit-QM wurde das Factoring als dramatische Wendung in dieser Forschung angesehen. Mit anderen Worten, das Problem, was effizient berechnet wird, reicht plausibel bis zu den Prinzipien der Tiefenphysik und bezieht sich darauf, ob Quantencomputer effizienter rechnen können als klassische Berechnungen, was auch ein allgemein offenes Problem in der theoretischen CS und der fortgeschrittenen Physik ist.

Man kann also sogar hinzufügen, dass P gegen NP und die Frage des effizienten Rechnens von entscheidender oder grundlegender Bedeutung sein können, zusätzlich zu CS und Mathematik - Physik .

[1] P vs NP-Problem, Wikipedia

[2] Probleme mit Millenniumspreisen

[3] P / Poly-Klasse, Wikipedia

[4] Shors Algorithmus

Polynomialzeit-Algorithmen gelten nur im Vergleich mit der härtesten nichtpolynomialen Zeit, insbesondere der sogenannten NP-Complete, als effizient. Siehe Abbildung: Euler-Diagramm für P-, NP-, NP-vollständige und NP-harte Problemmengen .