Beispiele für Probleme, bei denen Exponentialalgorithmen für praktische Größen schneller ausgeführt werden als Polynomalgorithmen?

13

Kennen Sie Probleme (vorzugsweise zumindest einigermaßen bekannte), bei denen für eine praktische Problemgröße ein Exponentialalgorithmus viel schneller ausgeführt wird als ein bekanntes Gegenstück zur Polynomzeit.

Angenommen, ein Problem hat eine praktische Größe * von und es gibt zwei bekannte Algorithmen: Einer ist und der andere ist für eine Konstante . Es ist klar, dass für der Exponentialalgorithmus bevorzugt wird.2 n n c c c > 15n=1002nnccc>15

* Ich denke, praktische Größe würde etwas bedeuten, das in der realen Welt häufig anzutreffen ist. Wie die Anzahl der Züge in einem Netzwerk.

Ozzah
quelle
1
Ich denke, Sie finden, was Sie suchen, in der Literatur zur parametrisierten Komplexität.
Kaveh
Für lineare Algorithmen gibt es im Allgemeinen einen konstanten Multiplikator, der im Allgemeinen nicht signifikant ist und häufig aus der Komplexität herausgenommen wird. Ich erinnere mich jedoch, dass er sehr hoch erschien, als In-Place-Zusammenführung, die linear war, aber im schlimmsten Fall etwa 5000 N ... also in In diesen Szenarien gibt es einen großen nutzbaren Bereich, in dem N ^ 2 kleiner als 5000 N ist, in dem die Größe kleiner als sqrt (5000) ist, und eine kleinere Domäne, in der 2 ^ n noch schneller ist, in dem n kleiner als log 5000 ist
Grady Player

Antworten:

13

Wie steht es mit dem Simplex-Algorithmus für die lineare Programmierung? In vielen Fällen wird es in der Praxis eingesetzt.

Bearbeitet, um hinzuzufügen: Ich denke, es handelt sich eher um einen "Exponentialalgorithmus für den schlimmsten Fall", der auf praktischen Instanzen / Verteilungen effizient ausgeführt wird, anstatt auf konkurrierenden Instanzen von praktischer Größe schneller .

RB
quelle
4
@diesalbla - es kommt auf das genaue forum an. Unter Berufung auf Wikipedia "gaben Klee und Minty [32] 1972 ein Beispiel dafür, dass die von Dantzig formulierte Simplex-Methode im schlimmsten Fall eine Exponentialzeit ist".
RB
12

Der schnellste bekannte Algorithmus für das Problem, ob ein Graph eine knotenlose Einbettung aufweist, ist Miller und Naimi zuzuschreiben und ist die Exponentialzeit. Die Robertson-Seymour-Theorie besagt, dass es für dieses Problem einen -Algorithmus gibt; Um es aufzuschreiben, müssten wir jedoch die Liste der verbotenen Minderjährigen für knotenlose Einbettungen kennen. Selbst wenn wir diese Liste kennen würden, wäre der Exponentialzeit-Algorithmus für Diagramme mit angemessener Größe immer noch viel schneller, da es über 250 verbotene Minderjährige gibt, von denen einige recht groß sind.Ö(n3)

Peter Shor
quelle
5
2222|H|Ö(n3)H
1
Ö(n2)|H|
1
HG|H|
-3

Es gibt einige Beispiele für die (nicht wahrscheinliche / genaue) Erkennung / Prüfung von Primalitäten . Der AKS-Algorithmus war der erste Algorithmus für Primalitätstests, der in P gezeigt wurde. Er konkurriert mit einigen exponentiellen Zeitalgorithmen für "kleine" Eingaben nicht günstig. Die Details sind etwas knifflig, da dies im Allgemeinen die Implementierung der Algorithmen erfordert. Dies ist eine herausfordernde Aufgabe und kann von implementierungsspezifischen Aspekten abhängen.

Weitere Infos / Details / Refs zu dieser Frage:

vzn
quelle
6
Nach meinem Kenntnisstand sind die Algorithmen, mit denen AKS in der Praxis konkurriert, entweder randomisierte Polynome (Miller-Rabin, ECPP) oder deterministische Quasipolynome (Adleman-Pomerance-Rumeley). Nirgends annähernd exponentielle Zeit.
Emil Jeřábek unterstützt Monica
6
Die randomisierte Version von Miller-Rabin, die in der Praxis verwendet wird, hängt nicht von der relativen Luftfeuchtigkeit ab.
Emil Jeřábek unterstützt Monica
5
Das ist alles sehr wahr, hat aber nichts mit der ursprünglichen Frage zu tun.
Emil Jeřábek unterstützt Monica
2
Ja, das weiß ich alles. Und zum dritten Mal ist dies irrelevant. Die Frage fragt nach Exponentialzeit- Algorithmen, die in der Praxis mit einem bekannten Polynomzeit-Algorithmus (hier AKS) konkurrieren. Der einzige in der Praxis verwendete Exponential-Zeit-Primalitätstest-Algorithmus ist die Versuchsteilung, die für Zahlen jeder nichttrivialen Größe nicht wettbewerbsfähig ist. Die in der Praxis verwendeten Konkurrenzalgorithmen sind viel effizienter als Exponentialalgorithmen, obwohl sie nicht polynomiell (oder deterministisch oder bedingungslos) sind.
Emil Jeřábek unterstützt Monica
3
Was Äpfel und Orangen sind, ist der Vergleich von AKS (einem Algorithmus zum Testen der Primalität) mit GNFS (einem Faktorisierungsalgorithmus).
Emil Jeřábek unterstützt Monica