Tengo una pregunta P/NP.
He leído que si se encuentra que cualquier problema de NP tiene un algoritmo de tiempo polinomial, entonces podemos reducir cualquier otro problema de NP a una forma en la que podamos usar nuestro primer algoritmo para resolver el nuevo problema de NP en tiempo polinomial también.
No veo por qué este es el caso.
Ejemplo: problema del ciclo hamiltoniano y vendedor ambulante.
Si encontrara un algoritmo de tiempo polinomial para determinar la existencia de un ciclo hamiltoniano en un gráfico, todavía no veo cómo esto podría permitirme encontrar un recorrido TSP en un límite superior de tiempo polinomial. La cantidad de subgrafos que tendríamos que verificar iterativamente para un ciclo hamiltoniano es a menudo exponencial. Por lo general, es imposible crear un solo subgrafo que contenga todos los recorridos TSP potenciales bajo un límite dado y aún así solo contendría un circuito hamiltoniano.
Es un poco más abstracto que eso. De hecho, al principio no es obvio obtener un recorrido TSP resolviendo el problema del ciclo hamiltoniano; una cosa para recordar es que los problemas en NP son problemas de decisión.
La formulación de decisión de TSP es la siguiente: dada una instancia de TSP , hay un recorrido de duración como máximo ?
Esto significa que la reducción de TSP al ciclo hamiltoniano haría esto: toma una instancia de TSP y construye otro gráfico tal que tiene un recorrido de longitud como máximo si y si es hamiltoniano. Aquí puede que ni siquiera se parezca en absoluto, solo tiene que satisfacer la propiedad anterior. Entonces no le da un recorrido, solo responde la pregunta sí/no sobre la duración del recorrido en .
Supongamos que la respuesta es sí. Para obtener un recorrido TSP real de duración máxima , una cosa que se puede hacer es eliminar un borde de y vuelva a ejecutar la misma reducción. Si la respuesta es 'no', significa que debe estar en el recorrido. Si la respuesta es 'sí', significa que puede eliminar . Repites para cada borde uno tras otro hasta obtener el recorrido.
El teorema de Cook-Levin establece que la Satisfacción Booleana (SAT) es NP-completa.
La forma habitual de probar la completitud NP de un problema de decisión distinto al SAT es por reducción; es decir, al exhibir un algoritmo polinomial que transforma instancias de un problema NP-completo conocido en instancias "equivalentes" de . Luego se argumenta que un algoritmo polinomial para produciría un algoritmo polinomial para .
Este proceso de probar la completitud de NP por reducción produce un árbol de problemas de decisión en cuya raíz se encuentra SAT. Para TSP y Hamiltonian Cycle (HC), la parte relevante del árbol se ve así en la mayoría de las presentaciones:
Por ejemplo, esta es la cadena que se encuentra en el venerable Garey y Johnson y en varios libros de texto populares. De acuerdo con esta ruta en el árbol, es fácil transformar una instancia de HC en una instancia correspondiente de TSP. Sin embargo, el teorema de Cook-Levin nos dice que podemos reducir TSP a SAT, y desde allí, a través de la serie de reducciones que se muestran arriba, llegar a una instancia correspondiente de HC.
Entonces, el árbol de reducciones explícitas utilizado para probar la completitud induce (a través del teorema de Cook-Levin) un gráfico dirigido que está fuertemente conectado.
Como señaló @ManuelLafond, la instancia de HC que se obtiene al final de este recorrido no se verá inmediatamente relacionada con la instancia original de TSP, pero su tamaño estará limitado por un polinomio en el tamaño de la instancia de TSP, que es lo que importa.