Warum wird die Polynomzeit als "effizient" bezeichnet?

Question

Warum wird in der Informatik eine Komplexität, die höchstens Polynom ist, als effizient angesehen?

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

^{(a) Angenommen, die Anzahl der Atome im Universum beträgt beispielsweise ungefähr 10 $ {80} $.}

Answer 1

Eine weitere Perspektive auf "Effizienz" ist, dass die Polynomzeit es uns ermöglicht, einen Begriff der "Effizienz" zu definieren, der nicht von Maschinenmodellen abhängt. Insbesondere gibt es eine Variante der These der Kirche, die als "wirksame These der Kirchenenturteilung" bezeichnet wird, die besagt, dass jedes Problem, das in der Polynomzeit auf der Art des Maschinenmodells läuft, auch in der Polynomzeit auf einem anderen gleichwertigen Maschinenmodell läuft.

Dies ist eine schwächere Aussage zur allgemeinen CT Das Maschinenmodell.

Dies ist letztendlich der Grund, warum Polynomzeit ein populärer Begriff in Theorie ist. Die meisten Menschen erkennen jedoch, dass dies nicht die "praktische Effizienz" widerspiegelt. Weitere Informationen dazu, Dick Liptons Post on 'Galaktische Algorithmen'Ist eine tolle Lektüre.

Answer 2

Theoretisch kümmern wir uns um das asymptotische Verhalten und beschreiben Klassen von Problemen und Algorithmen basierend auf ihrem asymptotischen Verhalten. Das Schlüsselwort hier ist asymptotisch. $O(n^{80})$ is faster than $O(n^{log n})$ asymptotically, ie, starting from $n > 1208925819614629174706176$ (which by the way is called: septillion!), assuming unit Konstante Koeffizienten und keine Begriffe niedriger Ordnung.

In der Praxis wird jedoch sowohl den Exponenten als auch den konstanten Koeffizienten aufmerksam gemacht. In der Praxis können Eingabegrößen nicht auf Septillionen wachsen. Ja, $ n^{ log n} $ für alle Zwecke ist eine überlegene Wahl für $ n^{80} $. Andere Faktoren sind auch von Praktiken von Bedeutung: Parallelität, Speicherzugriffsmuster (z. B. Lokalität).

Zum Beispiel die meisten Bibliotheken für eine ganzzahlige Multiplikation, z. B. GMP Implementieren eine Mischung von Algorithmen und Wählen Sie minderwertige Algorithmus basierend auf der Eingangsgröße aus Wählen Sie die praktisch überlegenen Algorithmen basierend auf der Eingangsgröße aus, obwohl diese Algorithmen asymptotisch minderwertig sind. Einige asymptotisch "minderwertige" Algorithmen sind in bestimmten Eingangsgrößen schneller und werden über die optimalen Algorithmen ausgewählt.

Ein weiteres Beispiel: Der schnellste Matrix -Multiplikationsalgorithmus ist bekannt Coppersmith-Winograd-Algorithmus die in $ o (n^{2.3737}) $ läuft (es gibt kürzlich verbessert; mehr hier). Es wurde jedoch nie implementiert, weil (1) es schwierig ist (2) der konstante Koeffizient ist gigantisch. Alle linearen Algebra -Pakete verwenden das weniger optimale von Strassen.

TL; DR -Theorie kümmert sich um asymptotisches Verhalten, um Algorithmen zu vergleichen, wenn die Eingangsgrenze auf willkürlich große Zahlen geht.

Answer 3

Diese Antwort wird sich den Kontext Ihrer Frage "Größeres Bild" ansehen. Informatik ist eigentlich eine relativ junge und etwas offene Wissenschaft und hat noch keine großen oder gar guten Antworten auf einige grundlegende und grundlegende Fragen. Die grundlegende Frage "Was effizient berechnet wird" ist entweder genau oder grob Formalisiert in CS (abhängig von der Meinung) als berühmtes P -vs -NP offen Nach mehr als vier Jahrzehnten der ursprünglich von Cook/Levin ~ 1970 und intensiven Arbeiten der größten Informatiker der Welt (und viele Mathematiker interessieren sich auch für das Problem als grundlegend).

Also mit anderen Worten, auch mit einem Rau Definition von "effizient" als P -Zeit und einer der am höchsten wertvollen wissenschaftlichen Auszeichnungen - nämlich 1 Mio. USD für das Problem für über 10 Jahre - nicht einmal nachweisen, dass einige Probleme (in der Nähe dieser Grenzlinie) effizient haben müssen oder nicht (P -Zeit) Algorithmen. Daher ist die genaue Definition von "effizienter" genauer als die P -Zeit nicht erforderlich oder sogar möglich zu dieser Zeit. Wenn/wenn die P vs np -Vermutung auf die eine oder andere Weise festgelegt wird, kann eine strengere Definition von "effizienter" möglich sein oder vermutlich möglich sein.

Darüber hinaus könnte man das Gefühl haben, dass die P -Zeit Der Punkt, dass sie diese Behauptung oder Beobachtung sogar als trivial betrachten ... mit anderen Worten, sozusagen, Es ist eine Arbeit in Arbeit / Wir arbeiten daran. (In der Tat gehen die Mainstream-Informatiker sogar so weit, nur halb schädlich, routinemäßig die Lücke und den Mangel an Fortschritt/endgültige Trennungen als zu verweisen peinlich.)

In der Tat gibt es sogar ein eng verwandtes/deutlich stärker Vermutung als p vs np, nämlich NP gegen P/Poly, die zu diesem Zeitpunkt auch von der Informatik nicht aufgelöst werden kann. Es vermutet, dass NP-Zeitprobleme nicht gelöst werden können irgendein "P-Sized" -Kreise, dh nicht einmal auf die Schaltkreise beschränkt, die durch Algorithmen/Turing-Maschinen erstellt werden können.

Wie hart p vs np sein mag - es gibt einen soliden Grund zu der Annahme, dass es sein mag mindestens so hart als die sehr alte Riemann -Vermutung in Mathematik (jetzt 1.5 Jahrhundert Alt), weil beide seit über einem Jahrzehnt den gleichen $ 1 -Millionen -Preis haben und noch nicht gelöst wurden.

Mit anderen Worten, genau zu definieren, was Algorithmen wirklich "effizient" sind Wichtigste und am härteste vorhandene offene Probleme in der theoretischen Wissenschaft und Mathematik.

Tatsächlich ist die Frage, was effizient berechnet wird, noch subtiler, da es eine Variante der These zur CT-These der Kirche gibt, und es ist nicht bekannt, ob Quantum Computing tatsächlich verletzt es. Mit Shors bahnbrechendem Ergebnis von P-T-Time-QM betrachtete Factoring in dieser Forschung eine dramatische Wendung. Mit anderen Worten, das Problem, was effizient berechnet wird, steigt tatsächlich plausibel bis hin zu tiefen Physikprinzipien ab und bezieht sich darauf, ob das Quantencomputer effizienter berechnen kann als klassische Berechnungen, was auch ein allgemein offenes Problem in theoretischer CS und fortgeschrittener Physik ist.

Man kann also sogar hinzufügen, dass P vs NP & die Frage des effizienten Computers von entscheidender oder grundlegender Bedeutung sein kann, um in CS und Mathematik - hinzuzufügen - Physik.

[1] P gegen NP -Problem, Wikipedia

[2] Millenium Preisprobleme

[3] P/Poly -Klasse, Wikipedia

[4] Shors Algorithmus

Answer 4

Polynomzeitalgorithmen werden nur im Vergleich zu der schwierigsten nicht polynomialen Zeit als effizient angesehen, insbesondere mit der sogenannten NP-Complete. Siehe Bild: Euler-Diagramm für P-, NP-, NP-Complete- und NP-HARD-Satz von Problemen.