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
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.)
Para 9x9 Sudoku, não. Como é finito, pode ser resolvido no tempo O ( 1 )O(1) .
Mas se você tivesse um solucionador de n2× n2n2×n2 Sudoku, que trabalhou para todos nn 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 n2× n2n2×n2 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.
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
@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.
n2×n2n2×n2
@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.