Completitud NP y problemas NP

Question

Supongamos que alguien ha encontrado un algoritmo polinómico para un problema de decisión NP-completo. ¿Significaría esto que podemos modificar un poco el algoritmo y utilizarlo para resolver los problemas que están en NP, pero no en NP-completo? ¿O esto sólo muestra la disponibilidad de un algoritmo polinómico para cada problema NP indirectamente?

Editar: Sé que cuando los problemas NP-completos tienen algoritmos polinómicos, todos los problemas NP deben tener algoritmos polinómicos. La pregunta que me hago es si podemos utilizar el algoritmo descubierto para NP-completo a todos los problemas NP simplemente modificando el algoritmo. ¿O sólo sabríamos que los problemas NP deben tener un algoritmo polinómico indirectamente?

Answer 1

Un problema $X$ es "NP-completo" si para cualquier problema $Y$ en NP, existe una reducción en tiempo polinómico de $Y$ a $X$ . Por tanto, si existe un algoritmo de tiempo polinómico para algún problema de decisión NP-completo $X$ entonces hay un algoritmo relacionado para cualquier problema $Y$ en NP, es decir, reducir la instancia de $Y$ a una instancia de $X$ y utilizar el algoritmo de tiempo polinómico para $X$ .

Answer 2

Como NP-completo es un subconjunto de NP, la respuesta a tus dos preguntas es "sí". Supongamos que tenemos una solución determinista en tiempo real para un problema NP-completo $D$ . Entonces, por la definición de NP-completo, todo problema en NP podría ser reducido en tiempo poliédrico a $D$ Como cualquier problema NP-completo es, por definición, un problema NP, tendríamos entonces soluciones deterministas poli-tiempo para todos los problemas NP, incluidos los NP-completos. (Por no mencionar que entonces podrías escribir tu propio ticket de comida).