Entonces, el problema de decisión TSP (problema del vendedor ambulante) es NP completo .
Pero no entiendo cómo puedo verificar que una solución dada a TSP sea de hecho óptima en tiempo polinómico, dado que no hay forma de encontrar la solución óptima en tiempo polinómico (¿porque el problema no está en P)?
¿Algo que pueda ayudarme a ver que la verificación se puede hacer en tiempo polinomial?
El quid es que tienes que considerar el problema de decisión :
Para una instancia 'sí', el certificado es sólo un ciclo de Hamilton, cuyo peso es a lo sumo C . Si pudiera resolver este problema de manera eficiente, podría encontrar el costo de un recorrido mínimo por búsqueda binaria, comenzando con el peso de toda la red como un límite superior.
fuente
Probablemente esté pensando en el problema de determinar si una solución dada al TSP es la mejor solución. Sin embargo, no existe una solución polinómica conocida para esto, lo que significa que este problema está en NP-hard, pero no necesariamente NP-Complete.
El problema de decisión de TSP en realidad se trata de determinar si el peso de cualquier solución en un gráfico
G
tiene el mayor costoC
(como se explica mejor en la respuesta de Niel), lo que ciertamente es verificable en el tiempo polinómico.fuente
Puede demostrar que es óptimo dado un oráculo que resuelve el problema de decisión (ver otras respuestas) en tiempo polinómico al preguntar si existe una solución más corta. Si su objetivo es construir una solución óptima dado el oráculo, proceda de la siguiente manera. Encuentre el peso total mínimo a través de la búsqueda binaria (o si hay pesos de borde no enteros, encuentre un peso total que difiera del mínimo en menos de la diferencia mínima entre dos pesos de borde). Llame a este valor . Para cada borde en el gráfico, elimine el borde y consulte el oráculo para ver si todavía hay una solución de M como máximo . Si es así, deje el borde afuera y continúe. De lo contrario, vuelva a colocar el borde y continúe. Cuando haya procesado todos los bordes, le quedará un ciclo hamiltoniano de peso mínimo.
fuente