¿Qué problema de NP-Complete tiene el algoritmo más rápido conocido?

En términos de tiempo de ejecución asintótico en el peor de los casos, ¿qué problema de NP completo tiene el algoritmo (exacto) más rápido conocido y cuál es el algoritmo? ¿Hay algo conocido que sea más rápido que ? $O(n^2*2^n)$

algorithms reference-request np-complete Wuschelbeutel Kartoffelhuhn
fuente

¿Qué algoritmo tiene tiempo de ejecución ? EDITAR: Supongo que te refieres al algoritmo Held-Karp para el vendedor ambulante.

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

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

Guildenstern

Puede echar un vistazo a las respuestas a la pregunta ¿Existen algoritmos de tiempo subexponencial para problemas de NP completo? .

Pål GD

"Más rápido que " no tiene sentido. ¿Te refieres a ? O la pregunta es: "¿Existe un algoritmo con un límite de tiempo de ejecución superior mejor probado que ?"

O (_)

$O(\_)$

Θ

$\Theta$

O (_)

$O(\_)$

Raphael

El último. Es un punto válido; podría haber un algoritmo A que sea más rápido que B en la práctica, pero no con un límite superior más ajustado. No estoy seguro de por qué no tiene sentido decir "más rápido que un límite superior" en lugar de "más rápido que un límite inferior y superior" ...

Wuschelbeutel Kartoffelhuhn

Respuestas:

Vertex Cover tiene un algoritmo que se ejecuta en el tiempo , y por lo tanto es más rápido que , incluso con . Puede consultar la Tabla de carreras de FPT para obtener una breve lista de los tiempos de ejecución de FPT de diferentes problemas. Aquí, es el número de vértices es el tamaño de la solución. $1.2738^k + nk$ $2^n n^2$ $k=n$ $n$ $k$

Además, la pregunta ¿Existen algoritmos de tiempo subexponencial para problemas de NP completo? aborda preguntas similares.

Pål GD
fuente

Las preguntas se refiere a algoritmos más rápidos conocidos por la mesa y se vincula a que hace tener algoritmos "rápido" que el VC uno (en particular los subexponenciales), por lo que probablemente no es la mejor para citar.

Raphael

Vea también esta pregunta similar y la respuesta de David Eppstein Mejor tiempo de ejecución para resolver un problema NP-Complete en mathoverflow.

Pål GD

@Raphael Sí, por ejemplo, Fill-In mínimo tiene un algoritmo que para cada , se ejecuta en tiempo .

ϵ > 0

$\epsilon > 0$

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

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

Pål GD