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 > 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.
Antworten:
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 .
quelle
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.O ( n3)
quelle
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:
quelle