Mejor de los casos se ejecuta en tiempo para resolver un problema NP-completo?

Question

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

Tengo curiosidad acerca de las soluciones exactas y no aproximaciones.

Answer 1

  

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

Ordenar de. Usted puede deshacerse de cualquier factor de polinomio mediante la creación de un problema artificial que codifica la misma solución en una entrada polinómicamente más grande. Mientras la entrada es solamente polinomialmente más grande, el problema resultante es todavía NP-completo. Dado que la complejidad es, por definición, la función que mapea tamaño de entrada para el tiempo de funcionamiento, si el tamaño de entrada crece la función se pone en clases S inferiores.

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

Answer 2

Una característica de los problemas NP-completo es que ninguno de los problemas en NP puede ser transformado mecánicamente en cualquiera de los problemas NP-completos en, como máximo, tiempo polinómico.

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

Dado que la programación dinámica puede resolver Problema del viajante de 2 ^ tiempo ny 2 ^ N-Space, el mismo debe ser cierto para todos los demás problemas NP [Bueno, más el tiempo para aplicar la transformación, supongo - por lo que podría ser 2 ^ (n + 1)].

Answer 3

En general, usted no puede encontrar los mejores solución para el problema del viajante genérica sin probar todas las combinaciones (que podría ser distancias negativas, etc.).

Al añadir restricciones adicionales y aflojando el requisito de obtener el mejor solución, puede acelerar las cosas un poco.

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