Si puedo resolver Sudoku, ¿puedo resolver el problema del vendedor ambulante (TSP)? ¿Si es así, cómo?

Digamos que hay un programa tal que si le das un Sudoku parcialmente lleno de cualquier tamaño, te da el Sudoku completo correspondiente.

¿Puedes tratar este programa como una caja negra y usar esto para resolver TSP? Quiero decir, ¿hay alguna manera de representar el problema de TSP como Sudoku parcialmente lleno, de modo que si te doy la respuesta de ese Sudoku, puedes decir la solución para TSP en tiempo polinómico?

Si es así, ¿cómo? ¿Cómo se representa TSP como un Sudoku parcialmente lleno e interpreta el Sudoku lleno correspondiente para el resultado?

algorithms np-complete reductions traveling-salesman sudoku Chakrapani N Rao
fuente

Este artículo pretende ofrecer una reducción constructiva del Sudoku al problema del ciclo hamiltoniano: sciencedirect.com/science/article/pii/S097286001630038X

cwindolf

@ C.Windolf La pregunta es pedir la otra dirección. (De hecho, hay una respuesta eliminada que cometió el mismo error y citó el mismo artículo.)

David Richerby

Respuestas:

Para 9x9 Sudoku, no. Es finito, por lo que puede resolverse en $O(1)$ tiempo.

Pero si tuviera un programa de solución de $n^2 \times n^2$ Sudoku, que trabajó para toda $n$ y todos los posibles cuadros parciales, y corrió en tiempo polinómico, entonces sí, que podría ser utilizado para resolver TSP en tiempo polinómico, como completar a $n^2 \times n^2$ Sudoku es NP-completo.

La prueba de la completitud de NP funciona reduciendo de algún problema R de NP completo a Sudoku; entonces, dado que R es NP-completo, puede reducir de TSP a R (que se deduce de la definición de NP-completitud); y encadenar esas reducciones le brinda una forma de usar el solucionador de Sudoku para resolver TSP.

DW
fuente

¿Podría explicar cómo? Sí, supongamos que tengo un solucionador de sudoku general que actúa como una caja negra. Entonces, ¿cómo puedes usarlo? ¿Cómo representas a TSP como un Sudoku parcialmente lleno

Chakrapani N Rao

@ ChakrapaniNRao, ver respuesta actualizada. Sí, entiendo que es una caja negra. Para resolver los detalles, encuentre la prueba de integridad de NP para Sudoku y comprenda cómo funciona la reducción.

@ChakrapaniNRao No responde la pregunta por completo, pero la respuesta completa sería ridículamente larga, estaría llena de detalles intrincados y no le daría más iluminación que el bosquejo aquí. Es posible que una reducción de algún problema de NP completo a sudoku pueda ser interesante, pero, a menos que la prueba de que sudoku sea NP- completo fue en realidad una reducción de TSP (poco probable), la respuesta sigue siendo para terminar "y luego encadenar esas dos reducciones".

n^{2} \times n^{2}

$n^2\times n^2$

David Richerby

@ChakrapaniNRao Estás preguntando cómo resolver el problema X usando una caja negra para el problema Y. Eso es, literalmente, pedir una reducción. Eso es lo que significa "reducción". Y, como explica esta respuesta, la respuesta a su pregunta sí / no es sí.

David Richerby

@SolomonUcko, bueno, no, no necesariamente. La pregunta es: si tenemos un solucionador de Sudoku, ¿podemos usarlo para resolver TSP? La respuesta es sí, podemos. Te explico cómo. Esto le dará una manera de resolver TSP tan rápido como el solucionador de Sudoku resolverá Sudoku. Si el solucionador de Sudoku se ejecuta en tiempo polinómico, esto le dará una forma de resolver TSP en tiempo polinómico. Si el solucionador de Sudoku se ejecuta en tiempo subexponencial, esto le dará una forma de resolver TSP en tiempo subexponencial. Y así.

De hecho, es posible utilizar un solucionador de Sudoku general para resolver instancias de TSP, y si este solucionador toma tiempo polinómico, entonces todo el proceso también lo hará (en términos de complejidad, hay una reducción de tiempo polinomial de TSP a Sudoku). Esto se debe a que Sudoku tiene NP completo y TSP está en NP. Pero como suele ser el caso en esta área, mirar los detalles de la reducción no es particularmente esclarecedor. Si lo desea, puede juntarlo usando la reducción simple de la finalización del cuadrado latino a Sudoku aquí , la reducción de la triangulación de gráficos tripartitos uniformes a la finalización del cuadrado latino aquí , la reducción de 3SAT a la triangulación aquí, y una formulación de TSP como un problema 3SAT. Sin embargo, si desea comprender la idea detrás de la reducción de Sudoku a TSP, creo que sería mejor estudiar el teorema de Cook (que muestra que SAT es NP-completo) y un par de reducciones simples de 3SAT (p. Ej., A la correspondencia tridimensional) y estar satisfecho al saber que la reducción de TSP-Sudoku es exactamente el mismo tipo de cosas, pero más larga y más complicada.

rlms
fuente