Se eu puder resolver o Sudoku, posso resolver o Problema do Vendedor em Viagem (TSP)? Se sim, como?

Digamos que exista um programa que, se você der um Sudoku parcialmente preenchido de qualquer tamanho, ele fornecerá o Sudoku completo correspondente.

Você pode tratar esse programa como uma caixa preta e usá-lo para resolver o TSP? Quero dizer, existe uma maneira de representar o problema do TSP como Sudoku parcialmente preenchido, para que, se eu lhe der a resposta desse Sudoku, você possa dizer a solução para o TSP em tempo polinomial?

Se sim, como? como você representa o TSP como um Sudoku parcialmente preenchido e interpreta o Sudoku preenchido correspondente para o resultado.

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

Este artigo pretende dar uma redução construtiva do problema do ciclo Sudoku para o Hamiltoniano: sciencedirect.com/science/article/pii/S097286001630038X

cwindolf

@ C.Windolf A pergunta está pedindo a outra direção. (De fato, há uma resposta excluída que cometeu o mesmo erro e citou o mesmo artigo.)

David Richerby

Respostas:

Para 9x9 Sudoku, não. Como é finito, pode ser resolvido no tempo $O(1)$ .

Mas se você tivesse um solucionador de $n^2 \times n^2$ Sudoku, que trabalhou para todos $n$ e todas as placas parciais possíveis, e correu em tempo polinomial, então sim, que poderia ser usado para resolver TSP em tempo polinomial, como completar um $n^2 \times n^2$ Sudoku é NP-completo.

A prova da completude do NP funciona reduzindo de um problema completo do NP R para o Sudoku; então, como R é NP-completo, você pode reduzir de TSP para R (que segue a definição de NP-completude); e encadear essas reduções oferece uma maneira de usar o resolvedor Sudoku para resolver o TSP.

DW
fonte

Poderia explicar como? Sim, vamos supor que eu tenha o solucionador geral de sudoku, que funciona como uma caixa preta. Então, como você pode usá-lo? Como você representa o TSP como um Sudoku parcialmente preenchido

Chakrapani N Rao

@ChakrapaniNRao, veja a resposta atualizada. Sim, eu entendo que é uma caixa preta. Para descobrir os detalhes, encontre a prova de completude do NP para o Sudoku e entenda como a redução funciona.

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

$n^2\times n^2$

@ChakrapaniNRao Você está perguntando como resolver o problema X usando uma caixa preta para o problema Y. Isso está literalmente pedindo uma redução. É isso que significa "redução". E, como essa resposta explica, a resposta à sua pergunta sim / não é sim.

David Richerby 15/03

@SolomonUcko, bem, não, não necessariamente. As perguntas são as seguintes: se temos um solucionador de Sudoku, podemos usá-lo para resolver o TSP? A resposta é sim, nós podemos. Eu explico como. Isso fornecerá uma maneira de resolver o TSP tão rápido quanto o solucionador do Sudoku resolverá o Sudoku. Se o solucionador Sudoku for executado em tempo polinomial, isso permitirá que você resolva o TSP em tempo polinomial. Se o solucionador Sudoku for executado em tempo subexponencial, isso permitirá que você resolva o TSP em tempo subexponencial. E assim por diante.

É realmente possível usar um solucionador geral do Sudoku para resolver instâncias do TSP, e se esse solucionador levar tempo polinomial, todo o processo também será (na terminologia de complexidade, há uma redução no tempo polinomial do TSP para o Sudoku). Isso ocorre porque o Sudoku é NP completo e o TSP está no NP. Mas, como é geralmente o caso nesta área, observar os detalhes da redução não é particularmente esclarecedor. Se quiser, você pode juntar tudo usando a redução simples da conclusão do quadrado latino para o Sudoku aqui , a redução dos gráficos tripartidos uniformes triangulares para a conclusão do quadrado latino aqui , a redução do 3SAT para a triangulação aquie uma formulação de TSP como um problema 3SAT. No entanto, se você quiser entender a idéia por trás da redução do Sudoku para o TSP, acho que seria melhor estudar o teorema de Cook (mostrando que o SAT é NP-completo) e algumas reduções simples do 3SAT (por exemplo, correspondência tridimensional) e satisfeito com o fato de que a redução do TSP-Sudoku é exatamente o mesmo tipo de coisa, mas é mais longa e mais complicada.

rlms
fonte