Si je peux résoudre Sudoku, puis-je résoudre le problème du voyageur de commerce (TSP)? Si c'est le cas, comment?

Disons qu'il existe un programme tel que si vous donnez un Sudoku partiellement rempli de n'importe quelle taille, il vous donne le Sudoku complet correspondant.

Pouvez-vous traiter ce programme comme une boîte noire et l'utiliser pour résoudre le TSP? Je veux dire, y a-t-il un moyen de représenter le problème TSP comme un Sudoku partiellement rempli, de sorte que si je vous donne la réponse de ce Sudoku, vous pouvez dire la solution pour le TSP en temps polynomial?

Si oui, comment? comment représenter le TSP comme un Sudoku partiellement rempli et interpréter le Sudoku rempli correspondant pour le résultat.

algorithms np-complete reductions traveling-salesman sudoku Chakrapani N Rao
la source

Cet article prétend donner une réduction constructive du Sudoku au problème du cycle hamiltonien: sciencedirect.com/science/article/pii/S097286001630038X

cwindolf

@ C.Windolf La question demande l'autre sens. (En effet, il y a une réponse supprimée qui a fait la même erreur et a cité le même document.)

David Richerby

Réponses:

Pour le Sudoku 9x9, non. Il est fini et peut donc être résolu en temps $O(1)$ .

Mais si vous aviez un solveur pour $n^2 \times n^2$ Sudoku, qui fonctionnait pour toutes les $n$ et toutes les cartes partielles possibles, et fonctionnait en temps polynomial, alors oui, cela pourrait être utilisé pour résoudre TSP en temps polynomial, comme compléter un $n^2 \times n^2$ Sudoku est NP-complet.

La preuve de la complétude de NP fonctionne en réduisant d'un problème R de NP-complet à Sudoku; puis parce que R est NP-complet, vous pouvez passer de TSP à R (qui découle de la définition de NP-complétude); et le chaînage de ces réductions vous permet d'utiliser le solveur Sudoku pour résoudre TSP.

DW
la source

Pourriez-vous expliquer comment? Oui, supposons que j'ai un solveur sudoku général qui agit comme une boîte noire. Alors, comment pouvez-vous l'utiliser? Comment représentez-vous TSP en tant que Sudoku partiellement rempli

Chakrapani N Rao

@ChakrapaniNRao, voir la réponse mise à jour. Oui, je comprends que c'est une boîte noire. Pour trouver les détails, trouvez la preuve de la complétude NP pour Sudoku et comprenez comment fonctionne la réduction.

@ChakrapaniNRao Cela ne répond pas complètement à la question, mais la réponse complète serait ridiculement longue, pleine de détails complexes et ne vous donnerait pas plus d'éclaircissements que le croquis ici. Il est possible qu'une réduction de certains problèmes de NP à

sudoku soit intéressante, mais, à moins que la preuve que le sudoku ne soit

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

$n^2\times n^2$ NP ne soit complète était en fait par réduction de TSP (peu probable), la réponse va toujours se terminer " puis enchaîner ces deux réductions ".

David Richerby

@ChakrapaniNRao Vous demandez comment résoudre le problème X en utilisant une boîte noire pour le problème Y. Cela demande littéralement une réduction. Voilà ce que signifie «réduction». Et, comme l'explique cette réponse, la réponse à votre question oui / non est oui.

David Richerby

@SolomonUcko, eh bien, non, pas nécessairement. La question demande: si nous avons un solveur Sudoku, pouvons-nous l'utiliser pour résoudre TSP? La réponse est oui, nous le pouvons. J'explique comment. Cela vous donnera un moyen de résoudre TSP aussi rapidement que le solveur Sudoku résoudra Sudoku. Si le solveur Sudoku s'exécute en temps polynomial, cela vous donnera un moyen de résoudre TSP en temps polynomial. Si le solveur Sudoku s'exécute en temps sous-exponentiel, cela vous donnera un moyen de résoudre TSP en temps sous-exponentiel. Etc.

Il est en effet possible d'utiliser un solveur général de Sudoku pour résoudre des instances de TSP, et si ce solveur prend du temps polynomial, alors tout le processus le sera également (dans la terminologie de la complexité, il y a une réduction du temps polynomial du TSP au Sudoku). En effet, Sudoku est NP-complete et TSP est en NP. Mais comme c'est généralement le cas dans ce domaine, regarder les détails de la réduction n'est pas particulièrement éclairant. Si vous le souhaitez, vous pouvez l'assembler en utilisant la réduction simple de l'achèvement du carré latin au Sudoku ici , la réduction de la triangulation des graphiques tripartites uniformes à l'achèvement du carré latin ici , la réduction de 3SAT à la triangulation iciet une formulation du TSP comme problème 3SAT. Cependant, si vous voulez comprendre l'idée derrière la réduction du Sudoku au TSP, je pense que vous feriez mieux d'étudier le théorème de Cook (montrant que SAT est NP-complet) et quelques réductions simples de 3SAT (par exemple, pour une correspondance en 3 dimensions) et être satisfait de savoir que la réduction TSP-Sudoku est exactement le même genre de chose mais plus longue et plus délicate.

rlms
la source