¿Cómo se puede verificar el problema del vendedor ambulante en el tiempo polinómico?

Entonces entiendo la idea de que el problema de decisión se define como

¿Existe una ruta P tal que el costo sea menor que C?

y puede verificar fácilmente que esto sea cierto al verificar la ruta que recibe.

Sin embargo, ¿qué pasa si no hay un camino que se ajuste a este criterio? ¿Cómo verificaría la respuesta de "no" sin resolver el mejor problema de TSP de ruta y descubrir que el mejor tiene un costo peor que C?

complexity-theory time-complexity np decision-problem traveling-salesman wjmccann
fuente

Personalmente, solo había escuchado que la clase NP significaba verificación de tiempo múltiple, pero nunca había visto la restricción de que eso solo significa verificar las respuestas de "sí, aquí está la solución". Parece intuitivo imaginar que tienes que poder verificar cualquier solución en poly-time.

wjmccann

Respuestas:

NP es la clase de problemas donde puede verificar instancias de "sí". No se garantiza que pueda verificar instancias "no".

$C$

Hay algunos problemas, como la factorización de enteros y cualquier problema en P , que sabemos que están en NP y co-NP . (Gracias a user21820 por señalar esto).

No se sabe si NP y co-NP son el mismo conjunto de problemas. Si son iguales, entonces podemos verificar las instancias de "sí" y "no" de TSP. Si son diferentes, entonces P $\,\neq\,$ NP , ya que sabemos que P $\,=\,$ co-P (porque podemos negar la respuesta de una máquina determinista, dando la respuesta al problema del complemento).

David Richerby
fuente

Vale la pena mencionar que conocemos algunos problemas que están tanto en NP como en coNP, pero que no sabemos si están en P o no, como la factorización de enteros.

user21820

@ user21820 La factorización de enteros no es un problema de decisión. La originalidad es un problema de decisión y durante años se supo que estaba tanto en NP como en co-NP . Eventualmente se demostró estar en P también. No sé si todavía hay problemas que se sabe que tanto en NP y co-NP sin haber demostrado ser en P .

kasperd

@kasperd: Es un hecho bien conocido que la factorización de enteros cuando se convierte en un problema de decisión (¿n tiene un factor primo menor que m?) está tanto en NP como en coNP (ambas instancias sí / no pueden verificarse en tiempo polinómico a través de la prueba de primalidad AKS dada la factorización prima como certificado), pero aún no se muestra en P.

user21820

@ user21820 Hay formas mucho más simples y rápidas de verificar una factorización que AKS.

kasperd

@kasperd: Me gustaría saber esto. Para verificar una factorización, necesitaría, por ejemplo, los factores primos y para cada factor primo una prueba de que es primo.

gnasher729

"¿Cómo se puede verificar el problema del vendedor ambulante en tiempo polinómico?"

Ya sea en la forma en que lo describe, o no se sabe que sea así.

"Sin embargo, ¿qué pasa si no hay un camino que se ajuste a este criterio?"

En ese caso, para todas las máquinas NP para el problema de decisión, la máquina devolverá no para todos los certificados de candidato.

"¿Cómo verificaría la respuesta de" no "sin resolver el mejor problema de TSP de ruta y descubrir que el mejor tiene un costo peor que C?"

Bueno, uno podría recibir una prueba interactiva de que no existen tales caminos .

No se sabe que el problema que usted describe, TSP, esté en coNP , por lo que no se sabe que haya una forma "similar a NP" de verificar que no existe tal camino.

Juho
fuente