Sudoku è riducibile a SAT quindi è NP-Completo
Posted by: Andrea L. in didattica, software, tags: compuational complexity, np-complete, sat, sudokuVa di moda nelle keyword più usate per accede al mio sito la tupla “Sudoku np-completo” e devo dire che la curiosità per questo rompicapo si fa risentire.
Già nel novembre del 2005 scrissi qualcosa sulla NP-Completezza di Sudoku, senza approfondire troppo in verità, ora è il caso di aggiornare un pò di link
Innanzi tutto sempre grazie al fidato Google Scholar scopro una interessante articolo che generalizza il problema sudoku su di una matrice n x n e lo riduce a SAT (vi fornisco un link per scoprire cosa questo comporti).
Da qui ovviamente riesumando Cook possiamo asserire che Sudoku è un problema NP-Completo.
Per approfondire l’argomento vi lascio il link alla tesi di Takayuki Yato dell’Università di Tokyo o se volete potete dare uno sguardo all’algoritmo risolutivo, magari capite che l’informatica teorica è pane per il vostro futuro 
Entries (RSS)
[...] Date un’occhiata al nuovo post [...]
Tu va a vedere che si scopre che il Sudoku appartiene anche a P e ti porti a casa pure un milione di $ (con 6 zeri
)
Nel caso questo succeda… ricordati di chi t’ha sempre voluto bene!!
beh…non c’è che dire….io ero un appassionato del gioco, ora da informatico ho l’obbligo morale di lavorarci sopra, perchè se trovo un algoritmo polinomiale per risolverlo divento ricco!!!!!!!!!!!
[Yoga mode=on]
Limitarti tu non devi, un novello Turing milionario magari sarai
[/Yoda]
Quote: [Innanzi tutto sempre grazie al fidato Google Scholar scopro una interessante articolo che generalizza il problema sudoku su di una matrice n x n e lo riduce a SAT (vi fornisco un link per scoprire cosa questo comporti).
Da qui ovviamente riesumando Cook possiamo asserire che Sudoku è un problema NP-Completo.]
Il sudoku è NP-Completo se troviamo una trasformazione polinomiale dal SAT al sudoku, non dal sudoku al SAT.
Avendo dimostrato in precedenza che ogni problema NP è riducibile polinomialmente al SAT questo diventa NP-C.
In teoria il sudoku è solo NP…ma neanche questo è detto…
P (è contenuto in) NP quindi anche un problema in P si può ridurre polinomialmente in un problema NP.
Per transitività x~y e y~z => x~z e non x~y e z~y => x~z dato che non è stato dimostrato che la trasformazione polinomiale è simmetrica.