Który problem NP-Complete ma najszybszy znany algorytm?

Jeśli chodzi o najgorszy przypadek asymptotycznego środowiska uruchomieniowego, który problem NP-zupełny ma najszybszy znany (dokładny) algorytm i jaki jest algorytm? Czy jest coś znanego, co jest szybsze niż ? $O(n^2*2^n)$

algorithms reference-request np-complete Wuschelbeutel Kartoffelhuhn
źródło

Jaki algorytm ma czas działania ? EDYCJA: Zakładam, że masz na myśli algorytm Held – Karp dla Podróżującego Sprzedawcy.

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

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

Guildenstern

Możesz spojrzeć na odpowiedzi na pytanie Czy istnieją algorytmy czasu podwykładniczego dla problemów NP-zupełnych? .

Pål GD

„Szybszy niż ” nie ma sensu. Masz na myśli ? A może pytanie: „Czy istnieje algorytm z lepiej sprawdzonym górnym limitem czasu wykonywania niż ?”

O (_)

$O(\_)$

Θ

$\Theta$

O (_)

$O(\_)$

Raphael

Ten ostatni. To ważny punkt; może istnieć algorytm A, który w praktyce jest szybszy niż B, ale nie ma ściślejszej górnej granicy. Nie jestem pewien, dlaczego nie ma sensu mówić „szybciej niż górna granica” zamiast „szybciej niż dolna AND górna granica” ...

Wuschelbeutel Kartoffelhuhn

Odpowiedzi:

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

Ponadto pytanie Czy istnieją algorytmy czasu podwykładniczego dla problemów z NP-zupełnym? odpowiada na podobne pytania.

Pål GD
źródło

Pytania dotyczą najszybszych znanych algorytmów, a tabela, do której prowadzi łącze , ma algorytmy „szybsze” niż algorytm VC (w szczególności te z subeksponencjami), więc prawdopodobnie nie najlepiej jest cytować.

Raphael

Zobacz także to podobne pytanie i odpowiedź Davida Eppsteina Najlepszy czas działania, aby rozwiązać problem NP-Complete na matematycznym przepływie.

Pål GD

ϵ > 0

$\epsilon > 0$

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

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