Quel problème NP-Complete possède l'algorithme le plus rapide connu?

En termes d'exécution asymptotique dans le pire des cas, quel problème NP-complet a l'algorithme le plus rapide connu (exact) et quel est l'algorithme? Existe-t-il quelque chose de plus rapide que ? $O(n^2*2^n)$

algorithms reference-request np-complete Wuschelbeutel Kartoffelhuhn
la source

Quel algorithme a le temps d'exécution

? EDIT: Je suppose que vous voulez dire l'algorithme Held – Karp pour Traveller Salesman.

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

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

Guildenstern

Vous pouvez jeter un œil aux réponses à la question Existe-t-il des algorithmes à temps sous-exponentiel pour les problèmes NP-complets? .

Pål GD

"Plus rapide que

" n'a pas de sens. Vous voulez dire ? Ou est la question: «Existe-t-il un algorithme avec une limite d'exécution supérieure mieux éprouvée que ?

O (_)

$O(\_)$

Θ

$\Theta$

O (_)

$O(\_)$

Raphael

Le dernier. C'est un point valable; il pourrait y avoir un algorithme A plus rapide que B dans la pratique, mais pas avec une limite supérieure plus stricte. Je ne sais pas pourquoi cela n'a pas de sens de dire "plus vite qu'une limite supérieure" plutôt que "plus vite qu'une limite inférieure ET supérieure" ...

Wuschelbeutel Kartoffelhuhn

Réponses:

$1.2738^k + nk$ $2^n n^2$ $k=n$ $n$ $k$

De plus, la question Existe-t-il des algorithmes à temps sous-exponentiel pour les problèmes NP-complets? aborde des questions similaires.

Pål GD
la source

Les questions le plus rapide demande des algorithmes connus et la table que vous lien vers n'avoir « plus rapide » algorithmes que le VC un (en particulier les sous - exponentielles), il est donc probablement pas le meilleur de citer.

Raphael

Voir aussi cette question similaire et la réponse de David Eppstein Best-case Running-time pour résoudre un problème NP-Complete sur mathoverflow.

Pål GD

ϵ > 0

$\epsilon > 0$

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

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