Mejor tiempo de ejecución para resolver un problema NP-Completo?

Question

¿Cuál es el algoritmo más rápido que existe para resolver un problema particular de NP-Complete? Por ejemplo, una implementación ingenua de travelling salesman es O (n!), Pero con programación dinámica se puede hacer en O (n^2 * 2^n). ¿Hay algún problema NP-Completo quizás "más fácil" que tenga un mejor tiempo de ejecución?

Tengo curiosidad acerca de las soluciones exactas, no de las aproximaciones.

Answer 1

[...] con la programación dinámica que se puede hacer en O (n^2 * 2^n). ¿Hay algún problema NP-Completo quizás "más fácil" que tenga un mejor tiempo de ejecución?

Tipo de. Puede deshacerse de cualquier factor polinomial al crear un problema artificial que codifica la misma solución en una entrada polinomialmente más grande. Siempre que la entrada sea solo polinomialmente más grande, el problema resultante sigue siendo NP-completo. Dado que la complejidad es, por definición, la función que mapea el tamaño de la entrada al tiempo de ejecución, si el tamaño de la entrada aumenta, la función entra en clases O más bajas.

Por lo tanto, el mismo algoritmo que se ejecuta en TSP con la entrada rellenada con n^2 bits inútiles, tendrá complejidad O (1 * 2^sqrt (n)).

Answer 2

Una característica de los problemas NP-Complete es que cualquiera de los problemas en NP puede transformarse mecánicamente en cualquiera de los problemas NP-Complete en, como máximo, el tiempo polinomial.

Por lo tanto, cualquiera que sea la mejor solución para cualquier problema NP-Complete dado, es automáticamente una solución igualmente buena para cualquier otro problema NP.

Dado que la programación dinámica puede resolver el Problema de Vendedor Viajero en 2^n tiempo y 2^n espacio, lo mismo debe ser cierto para todos los demás problemas NP [bueno, más el tiempo para aplicar la transformación, supongo - así que podría ser 2^(n + 1)].

Answer 3

Generalmente no puede encontrar la solución mejor para el problema genérico de Viajero de ventas sin probar todas las combinaciones (puede haber distancias negativas, etc.).

Al agregar restricciones adicionales y aflojar el requisito de obtener la mejor solución , puede acelerar un poco las cosas.

Por ejemplo, puede obtener tiempo polinomial ejecutable si las distancias en el problema obedecen al "no es más ir directamente de A a B que ir de A a B" (es decir, un atajo nunca es más largo), y puede vivir con el resultado máximo de 1,5 veces el valor óptimo. Ver http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP