Jika saya dapat memecahkan Sudoku, bisakah saya menyelesaikan Masalah Traveling Salesman Problem (TSP)? Jika ya, bagaimana caranya?

Katakanlah ada program sedemikian rupa sehingga jika Anda memberikan Sudoku yang terisi sebagian dari ukuran apa pun, itu memberi Anda Sudoku lengkap yang sesuai.

Bisakah Anda memperlakukan program ini sebagai kotak hitam dan menggunakannya untuk menyelesaikan TSP? Maksud saya, apakah ada cara untuk merepresentasikan masalah TSP sebagai Sudoku yang terisi sebagian, sehingga jika saya memberikan jawaban kepada Sudoku itu, Anda dapat memberi tahu solusi untuk TSP dalam waktu polinomial?

Jika ya, bagaimana? bagaimana Anda mewakili TSP sebagai Sudoku yang terisi sebagian dan menafsirkan Sudoku yang sesuai untuk hasilnya.

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

Makalah ini mengklaim memberikan pengurangan konstruktif dari Sudoku ke masalah siklus Hamilton: sciencedirect.com/science/article/pii/S097286001630038X

cwindolf

@ C.Windolf Pertanyaannya adalah menanyakan arah yang lain. (Memang, ada jawaban yang dihapus yang membuat kesalahan yang sama dan mengutip makalah yang sama.)

David Richerby

Jawaban:

Untuk 9x9 Sudoku, no. Itu terbatas sehingga dapat diselesaikan dalam waktu. $O(1)$

Tetapi jika Anda memiliki pemecah untuk Sudoku, yang bekerja untuk semua dan semua papan parsial yang mungkin, dan berlari dalam waktu polinomial, maka ya, yang dapat digunakan untuk memecahkan TSP dalam waktu polinomial, saat menyelesaikan a Sudoku adalah NP-complete. $n^2 \times n^2$ $n$ $n^2 \times n^2$

Bukti kelengkapan NP bekerja dengan mengurangi dari beberapa masalah NP-lengkap R ke Sudoku; kemudian karena R adalah NP-complete, Anda dapat mengurangi dari TSP ke R (yang mengikuti definisi NP-completeness); dan merantai pengurangan itu memberi Anda cara untuk menggunakan pemecah Sudoku untuk menyelesaikan TSP.

DW
sumber

Bisakah Anda jelaskan caranya? Ya mari kita asumsikan saya memiliki pemecah sudoku umum yang bertindak sebagai kotak hitam. Jadi bagaimana Anda bisa menggunakannya? Bagaimana Anda mewakili TSP sebagai Sudoku yang terisi sebagian

Chakrapani N Rao

@ ChakrapaniNRao, lihat jawaban yang diperbarui. Ya, saya mengerti itu kotak hitam. Untuk mengetahui detailnya, cari bukti kelengkapan NP untuk Sudoku dan pahami cara kerja reduksi.

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

$n^2\times n^2$

@ ChakrapaniNRao Anda bertanya bagaimana menyelesaikan masalah X menggunakan kotak hitam untuk masalah Y. Itu secara harfiah meminta pengurangan. Itulah arti "reduksi". Dan, seperti yang dijelaskan oleh jawaban ini, jawaban untuk pertanyaan ya / tidak Anda adalah ya.

David Richerby

@ SolomonUcko, well, tidak, belum tentu. Pertanyaannya bertanya: jika kita memiliki pemecah Sudoku, dapatkah kita menggunakannya untuk menyelesaikan TSP? Jawabannya adalah ya, kita bisa. Saya jelaskan caranya. Ini akan memberi Anda cara untuk menyelesaikan TSP secepat Solver Sudoku akan memecahkan Sudoku. Jika pemecah Sudoku berjalan dalam waktu polinomial, ini akan memberi Anda cara untuk menyelesaikan TSP dalam waktu polinomial. Jika pemecah Sudoku berjalan dalam waktu subeksponensial, ini akan memberi Anda cara untuk menyelesaikan TSP dalam waktu subeksponensial. Dan seterusnya.

Memang mungkin untuk menggunakan pemecah Sudoku umum untuk menyelesaikan contoh TSP, dan jika pemecah ini membutuhkan waktu polinomial maka seluruh proses juga (dalam terminologi kompleksitas, ada pengurangan waktu polinomial dari TSP ke Sudoku). Ini karena Sudoku NP-lengkap dan TSP di NP. Tetapi seperti yang biasanya terjadi di daerah ini, melihat detail pengurangan tidak terlalu mencerahkan. Jika Anda mau, Anda bisa menyatukannya dengan menggunakan reduksi sederhana dari pelengkapan kuadrat Latin ke Sudoku di sini , reduksi dari triangulasi grafik tripartit seragam menjadi pelengkap kuadrat Latin di sini , reduksi dari 3SAT menjadi triangulasi di sini, dan perumusan TSP sebagai masalah 3SAT. Namun, jika Anda ingin memahami ide di balik pengurangan dari Sudoku ke TSP saya pikir Anda akan lebih baik mempelajari teorema Cook (menunjukkan bahwa SAT adalah NP-complete) dan beberapa pengurangan sederhana dari 3SAT (misalnya pencocokan 3 dimensi) dan puas dalam pengetahuan bahwa pengurangan TSP-Sudoku adalah hal yang sama tetapi lebih lama dan lebih fiddly.

rlms
sumber