Best-Case-Laufzeit, um ein NP-vollständiges Problem zu lösen?

Question

Was ist der schnellste Algorithmus, der existiert, um ein bestimmtes NP-Complete-Problem zu lösen? Zum Beispiel ist eine naive Implementierung von travelling salesman O (n!), Aber mit dynamischer Programmierung kann es in O (n^2 * 2^n) gemacht werden. Gibt es vielleicht ein "einfacheres" NP-vollständiges Problem, das eine bessere Laufzeit hat?

Ich bin neugierig auf genaue Lösungen, keine Näherungswerte.

Answer 1

[...] mit dynamischer Programmierung kann es in O (n^2 * 2^n) gemacht werden. Gibt es vielleicht ein "einfacheres" NP-vollständiges Problem, das eine bessere Laufzeit hat?

Sortieren von. Sie können jeden Polynomfaktor loswerden, indem Sie ein künstliches Problem erzeugen, das dieselbe Lösung in einer polynomiell größeren Eingabe codiert. Solange die Eingabe nur polynomiell größer ist, ist das resultierende Problem immer noch NP-vollständig. Da die Komplexität per definitionem die Funktion ist, die die Eingabegröße der Laufzeit zuordnet, steigt die Funktion bei niedrigeren Eingabegrößen in niedrigere O-Klassen.

Also, derselbe Algorithmus, der auf TSP mit der Eingabe läuft, die mit n^2 nutzlosen Bits aufgefüllt wird, wird Komplexität O (1 * 2^sqrt (n)) haben.

Answer 2

Ein Merkmal der NP-vollständigen Probleme ist, dass jedes der Probleme in NP mechanisch in jedes der NP-vollständigen Probleme in höchstens polynomieller Zeit umgewandelt werden kann.

Daher ist die beste Lösung für jedes NP-Complete-Problem automatisch eine ähnlich gute Lösung für jedes andere NP-Problem.

Vorausgesetzt, dass dynamische Programmierung Travelling Salesman Problem in 2^n Zeit und 2^n Raum lösen kann, muss das gleiche für alle anderen NP-Probleme gelten [gut, plus die Zeit, um die Transformation anzuwenden, denke ich - so könnte 2^(n + 1)] sein.

Answer 3

Im Allgemeinen können Sie nicht die beste Lösung für das generische Travelling Salesman Problem finden, ohne alle Kombinationen auszuprobieren (es könnte negative Entfernungen geben, usw.).

Durch Hinzufügen zusätzlicher Einschränkungen und Lösen der Anforderung, die beste Lösung zu bekommen, können Sie die Dinge ziemlich beschleunigen.

Zum Beispiel können Sie polynomial ausführbare Zeit bekommen, wenn die Abstände in dem Problem gehorchen "es ist nicht länger, direkt von A nach B zu gehen als von A nach C nach B" (dh eine Abkürzung ist nie länger), und können Sie mit dem Ergebnis maximal 1,5 mal den optimalen Wert leben. Siehe http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP