Welches NP-Complete-Problem hat den schnellsten bekannten Algorithmus?

Welches NP-vollständige Problem hat in Bezug auf die asymptotische Laufzeit im schlimmsten Fall den schnellsten bekannten (exakten) Algorithmus und was ist der Algorithmus? Gibt es etwas bekanntes, das schneller ist als ? $O(n^2*2^n)$

algorithms reference-request np-complete Wuschelbeutel Kartoffelhuhn
quelle

Welcher Algorithmus hat die Laufzeit

? EDIT: Ich nehme an, Sie meinen den Held-Karp-Algorithmus für Travelling Salesman.

O (n^{2} \cdot 2^{n})

$O(n^2 \cdot 2^n)$

Guildenstern

Sie können sich die Antworten auf die Frage ansehen. Gibt es subexponentielle Zeitalgorithmen für NP-vollständige Probleme? .

Pål GD

"Schneller als

" macht keinen Sinn. Du meinst

? Oder lautet die Frage: "Gibt es einen Algorithmus mit einer besser nachgewiesenen oberen Laufzeitgrenze als

O (_)

$O(\_)$

Θ

$\Theta$

O (_)

$O(\_)$

Raphael

Letzteres. Es ist ein gültiger Punkt; Es könnte einen Algorithmus A geben, der in der Praxis schneller als B ist, jedoch nicht mit einer engeren Obergrenze. Ich bin mir nicht sicher, warum es keinen Sinn macht, "schneller als eine obere Schranke" statt "schneller als eine untere UND obere Schranke" zu sagen ...

Wuschelbeutel Kartoffelhuhn

Antworten:

Vertex Cover hat einen Algorithmus, der in der Zeit läuft , und ist daher auch mit schneller als . In der Tabelle der FPT-Rennen finden Sie eine kurze Liste der FPT-Laufzeiten für verschiedene Probleme. Hier ist die Anzahl der Eckpunkte und die Lösungsgröße. $1.2738^k + nk$ $2^n n^2$ $k=n$ $n$ $k$

Auch die Frage Gibt es subexponentielle Zeitalgorithmen für NP-vollständige Probleme? geht auf ähnliche Fragen ein.

Pål GD
quelle

Die Frage fragt nach den schnellsten bekannten Algorithmen, und die Tabelle, auf die Sie verweisen, enthält "schnellere" Algorithmen als die VC-Algorithmen (insbesondere subexponentielle). Daher ist es wahrscheinlich nicht die beste, diese zu zitieren.

Raphael

Siehe auch diese ähnliche Frage und David Eppsteins Antwort Best-Case-Laufzeit zur Lösung eines NP-Complete-Problems auf mathoverflow.

Pål GD

@Raphael Ja, zum Beispiel Minimum Fill-In hat einen Algorithmus, der für jedes

läuft .

ϵ > 0

$\epsilon > 0$

O ((1 + ϵ)^{k} + poly (n))

$O( (1+\epsilon)^k + \text{poly}(n))$

Pål GD