Warum sind die meisten (oder alle?) Polynomzeitalgorithmen praktisch?

Ich habe kürzlich in einem Artikel einen interessanten Kommentar darüber gelesen, wie seltsam nützlich Mathematik ist. Es wird erwähnt, dass Polynomzeit in der Realität nicht effizient bedeuten muss (z.$O(n^{999999999999999999999})$ist Polynomzeit, aber nicht effizient). Ist es nicht so, dass alle Algorithmen in der Polynomzeit, wie höchstens, auch realistisch sind?$O(n^4)$oder so? Ich denke meine Fragen sind:

1. Ist das überraschend?

2. Gibt es Beispiele für Algorithmen, die Polynomzeit haben, aber nicht praktikabel sind?

Der Kommentar ist falsch. Es ist sehr einfach, Beispiele für Polynomzeitalgorithmen zu nennen, die überhaupt nicht praktikabel sind:

1. Der Ellipsoidalgorithmus zum Lösen linearer Programme läuft in Polynomzeit, ist jedoch zu langsam, um praktisch zu sein. In der Praxis wird der Simplex-Algorithmus bevorzugt, dessen Laufzeit im ungünstigsten Fall exponentiell ist.

2. Der AKS-Primalitätstestalgorithmus wird in Polynomzeit ausgeführt, ist jedoch zu langsam, um praktisch zu sein. Stattdessen werden randomisierte Polynomzeitalgorithmen verwendet. Wir opfern Sicherheit für Leistung.

3. Schnelle Matrixmultiplikationsalgorithmen laufen asymptotisch schneller als High-School-Matrixmultiplikation (beide sind Polynome), aber zu langsam, um praktisch zu sein. Der High-School-Algorithmus wird in der Praxis verwendet.

4. Ein ähnliches Problem tritt bei schnellen ganzzahligen Multiplikationsalgorithmen auf. Der Algorithmus mit der besten asymptotischen Komplexität, Fürers Algorithmus, ist zu langsam, um in der Praxis verwendet zu werden. Stattdessen werden relativ einfache Algorithmen auch für ziemlich große ganze Zahlen verwendet.

5. Big-Data-Algorithmen müssen in linearithmischer Zeit ausgeführt werden $O(n \log^{O(1)}n)$) um praktisch zu sein.

Diese Beispiele zeigen, dass die Identifizierung der Polynomzeit mit der Praxis nicht genau ist und von den Umständen abhängen kann. Forscher in theoretischen Algorithmen haben das Bedürfnis, ihr Forschungsgebiet zu rechtfertigen, und glauben daher ideologisch an die Gefühle, die in dem von Ihnen erwähnten Kommentar zum Ausdruck kommen. Sie sollten solche Kommentare nicht zu wörtlich nehmen.

Tatsächlich sind viele in der Praxis verwendete Algorithmen heuristisch und wir haben keine Schätzungen zu ihrer Laufzeit außer empirischen Ergebnissen. Ein solcher Algorithmus passt überhaupt nicht in den theoretischen Rahmen, ist jedoch in der Praxis sehr nützlich. Einige (aber nicht alle) Algorithmen für maschinelles Lernen gehören zu dieser Klasse nur in Bezug auf die Laufzeit (ganz zu schweigen von der Leistung ), ebenso wie Suchalgorithmen wie A * und Alpha-Beta und SAT-Lösungsalgorithmen.

Frage (1) ist eine knifflige Frage, für die ich noch nie einen guten Grund gesehen habe. Ein Vorschlag könnte sein, dass wir die Antworten für einfachere Probleme viel eher verstehen und finden, je schwieriger spezielle Fähigkeiten sind, so dass die Chance, dass die richtige Person daran arbeitet und die Antwort findet, gering ist. Das ist alles sehr handwinkend.

Für (2) gibt es definitiv Beispiele, tatsächlich wurde diese Frage bereits gestellt und beantwortet! Beachten Sie auch, dass es eine Kette von Links zu einer cstheory.se-Frage und einer math.se-Frage gibt, die andere Beispiele enthalten.

Ich habe die folgende Erklärung zu Ihrer Frage (1) gesehen:

Die Kräfte von $n$in der Laufzeit entstehen meist aus for- Schleifen oder ähnlichen Konstrukten. Jede for- Schleife wird wiederum benötigt, da wir als Löser eine Idee hatten, wie wir das Problem auflösen oder über etwas Nützliches indizieren können. Da wir normalerweise nur eine kleine Anzahl von Ideen verwenden, sind die Kräfte tendenziell gering. Es ist schwer sich einen Algorithmus mit 20 verschachtelten for- Schleifen vorzustellen , bei dem wir innerhalb der allerletzten for- Schleife tatsächlich etwas tun, das von allen 20 Indizes abhängt.

Dieses Argument gefällt mir, ist aber ziemlich schwach, weil es sich nur um for- Schleifen handelt. Zum Beispiel kann man leicht eine beliebige Anzahl von verschachtelten for- Schleifen mit Rekursion erstellen , aber dann kann man gute Gründe gegen eine solch bizarre Konstruktion finden. Auf jeden Fall denke ich, dass dieses Argument durch eine Analyse vieler verschiedener Fälle gestärkt werden kann, aber ich präsentiere nur die Idee auf hoher Ebene.