Qual problema NP-Complete possui o algoritmo mais rápido conhecido?

Em termos de pior tempo de execução assintótico, qual problema de NP-completo possui o algoritmo mais rápido (exato) conhecido e qual é o algoritmo? Existe algo conhecido que é mais rápido que $O(n^2*2^n)$ ?

algorithms reference-request np-complete Wuschelbeutel Kartoffelhuhn
fonte

Qual algoritmo possui tempo de execução

? Edição: Eu suponho que você quer dizer o algoritmo Held – Karp para Travelling Salesman.

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

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

Guildenstern

Você pode dar uma olhada nas respostas para a pergunta Existem algoritmos de tempo subexponencial para problemas completos de NP? .

Pål GD

"Mais rápido que

" não faz sentido. Quer dizer

? Ou é a pergunta: "Existe um algoritmo com um limite de tempo de execução superior melhor comprovado que

O (_)

$O(\_)$

Θ

$\Theta$

O (_)

$O(\_)$

Raphael

O último. É ponto válido; poderia haver um algoritmo A mais rápido que B na prática, mas não com um limite superior mais apertado. Eu não sei por que não faz sentido dizer "mais rápido do que um limite superior" ao invés de "mais rápido do que um limite inferior e superior" ...

Wuschelbeutel Kartoffelhuhn

Respostas:

Vértice da tampa tem um algoritmo de execução em tempo , e é, portanto, mais rapidamente do que , mesmo com . Você pode conferir a Tabela de corridas do FPT para obter uma lista curta dos tempos de execução do FPT com diferentes problemas. Aqui, é o número de vértices é o tamanho da solução. $1.2738^k + nk$ $2^n n^2$ $k=n$ $n$ $k$

Além disso, a pergunta Existem algoritmos de tempo subexponencial para problemas de NP-completo? aborda questões semelhantes.

Pål GD
fonte

As perguntas pede algoritmos mais rápido conhecidas e a tabela que você conectar-se a não ter algoritmos "mais rápido" do que o VC um (em particular aqueles subexponencial), por isso não é provavelmente a melhor citar.

Raphael

Veja também essa pergunta semelhante e a resposta de David Eppstein Tempo de execução de melhor caso para resolver um problema NP-Complete no mathoverflow.

Gål GD

@Raphael Sim, por exemplo, o Fill-In Mínimo possui um algoritmo que para cada

, é executado no tempo

ϵ > 0

$\epsilon > 0$

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

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

precisa saber é o seguinte