Mejor tiempo en marcha para resolver un problema NP-completo

Question

¿Cuál es el algoritmo más rápido que existe para resolver un problema NP-completo? Por ejemplo, una aplicación ingenua de viajar a vendedor es $O(n!)$, pero con programación dinámica puede hacerse en $O(n^2 2^n)$. ¿Hay algún problema NP-completo "más fácil" que tiene un mejor tiempo?

Tenga en cuenta que tengo curiosidad sobre soluciones exactas, no aproximaciones.

Answer 1

Si P es un NP-completo problema, a continuación, definir P_k = instancias de P en el que las instancias han sido volado de tamaño n a de tamaño n^k mediante el relleno con espacios en blanco. Entonces P_k también es NP-completo, pero si P toma el tiempo de exp(p(n)) para resolver donde p es algún polinomio P_k puede ser resuelto en tiempo esencialmente exp(p(n^1/k)) (hay un poco más de tiempo necesario para comprobar que la entrada, realmente no tienen la cantidad de relleno, pero a menos que el tiempo de ejecución es el polinomio esta es una negligable fracción del tiempo total). Lo que no hay "más fácil" problema: para cada problema nombre de esta construcción se da otra más fácil, pero todavía NP-completos problema.

Como para no-artificiales problemas: la mayoría de los duros problemas de gráfico como circuito Hamiltoniano, que son difíciles cuando se limita a grafos planares, puede ser resuelto en tiempo exponencial en √n o en (√n)(log n) por programación dinámica utilizando una partición recursiva por la gráfica de los separadores.

Answer 2

Si P = NP, entonces existe un algoritmo de tiempo polinomial para resolver cualquier problema NP-completo dado. De lo contrario, se sabe que no existen algoritmos generales para cualquier problema NP-completo que son mejores que la media exponencial: es decir, f que (x) donde f(f(x)) es exponencial.