¿Cómo determinar el tiempo de ejecución polinomial de una reducción de NP?

Question

Para demostrar que un problema NP es NP-Complete, también tenemos que mostrar que $ L LEQ_ {P} L '$, donde $ L $ está probado NP-Complete y debe probar $ L' $ también. Lo que estoy confundido es cómo en todos los problemas completos de NP en CLRS simplemente indican el algoritmo de reducción de $ L $ para convertir a $ L '$ es polinomio. ¿Cómo se puede demostrar que es el tiempo polinomial, proporcionó un ejemplo de un problema de ciclo de camarilla o jamón?

Answer 1

El problema aquí es un malentendido del punto de la reducción. No se sabe que los problemas completos de NP tengan algoritmos de tiempo polinomiales. Si lo hacen, entonces p $ = $ np, si no lo hacen, entonces p $ neq $ np - este es el GRANDE cuestión de la informática teórica.

El objetivo de las reducciones que está viendo es demostrar que el problema $ L '$ es NP-completado y, por lo tanto, al menos tan difícil como cualquier otra cosa en NP. Hace esto demostrando que si podría resolver $ L '$ en tiempo polinomial, luego, utilizando la reducción, también podría resolver $ L $ en tiempo polinomial (tome la instancia de $ L $, conviértelo a una instancia de $ l' $, resuelva eso, luego use esa solución para obtener la solución a la instancia original).

Como $ L $ es NP-COMPLETO, esto también significa que si pudiéramos resolverlo en tiempo polinomial, podríamos resolver cada Problema en NP en el tiempo polinomial (de ahí la intuición de que los problemas completos de NP son, en cierto sentido, los problemas "más difíciles" en NP).

Solo para agregar algunos bits técnicos además de eso, un problema $ pi $ es NP-Complete si:

1. $ Pi en $ np, y
2. $ Pi $ es np-hard.

Un problema $ pi $ está en NP si hay un algoritmo no determinista que resuelve $ pi $ en tiempo polinómico en el tamaño de la entrada o de manera equivalente, podemos verificar una respuesta a una instancia de $ pi $ en determinista tiempo polinomial.

Un problema $ pi $ es np-hard si cada Problema $ phi en $ np, existe una reducción del tiempo polinomial de tal manera que $ phi leq_ {p} pi $ (esta puede ser una reducción diferente por cada $ phi $). En la práctica, lo que hacemos es encadenar estas reducciones juntas, así que digamos que tenemos un problema np-Hard $ pi '$, entonces sabemos que hay reducciones de todo en NP, así que si podemos mostrar que $ pi' leq_ {p} pi $ luego al componer las reducciones, podemos demostrar que hay una reducción de todo a $ pi $ (simplemente vamos a través de $ pi '$).

Entonces, para volver a la pregunta original, no sabemos si hay un algoritmo de tiempo polinómico por $ l '$ - la mayoría (?) La gente probablemente sospecharía que no hay, ya que mucha gente ha pasado mucho tiempo Tratando de encontrar incluso un algoritmo de tiempo polinómico para cualquier problema completo de NP y hasta ahora no ha habido suerte (por supuesto, tal algoritmo para cualquiera de ellos significa un algoritmo de tiempo polinómico para todo en np). La reducción 'Just' muestra que $ L '$ es uno de estos problemas difíciles.