Bagaimana masalah salesman keliling dapat diverifikasi dalam waktu polinomial?

21

Jadi saya mengerti ide bahwa masalah keputusan didefinisikan sebagai

Apakah ada jalur P sehingga biaya lebih rendah dari C?

dan Anda dapat dengan mudah memeriksa ini benar dengan memverifikasi jalur yang Anda terima.

Namun, bagaimana jika tidak ada jalur yang sesuai dengan kriteria ini? Bagaimana Anda memverifikasi jawaban "tidak" tanpa menyelesaikan jalan TSP masalah terbaik, dan menemukan yang terbaik memiliki biaya lebih buruk daripada C?

complexity-theory time-complexity np decision-problem traveling-salesman wjmccann
sumber
Secara pribadi, saya hanya mendengar NP kelas yang berarti verifikasi waktu-poli, tetapi belum pernah melihat batasan bahwa itu hanya berarti memverifikasi jawaban "ya, ini solusinya". Tampaknya intuitif untuk membayangkan bahwa Anda harus dapat memverifikasi solusi apa pun dalam waktu bersamaan.
wjmccann

Jawaban:

36

NP adalah kelas masalah di mana Anda dapat memverifikasi contoh "ya". Tidak ada jaminan yang diberikan bahwa Anda dapat memverifikasi contoh "tidak".

Kelas masalah di mana Anda dapat memverifikasi contoh "tidak" dalam waktu polinom adalah co-NP . Setiap bahasa dalam co-NP adalah pelengkap dari beberapa bahasa dalam NP , dan sebaliknya. Contohnya termasuk hal-hal seperti non-3-colourability. Masalah yang Anda gambarkan, "Apakah tidak ada jalur TSP dengan panjang paling banyak  ?" juga dalam NP bersama : jika Anda menghapus dua kali negasi, contoh "tidak" untuk masalah itu adalah contoh "ya" untuk TSP dan kami dapat memverifikasi mereka dalam waktu polinomial.C

Ada beberapa masalah, seperti faktorisasi bilangan bulat dan masalah apa pun dalam  P , yang kita tahu ada di NP dan co-NP . (Terima kasih kepada user21820 untuk menunjukkan ini.)

Tidak diketahui apakah NP dan co-NP merupakan set masalah yang sama. Jika mereka sama, maka kita dapat memverifikasi kedua "ya" dan "tidak" contoh TSP. Jika mereka berbeda, maka P≠NP , karena kita tahu bahwa P=co-P (karena kita bisa meniadakan jawaban dari mesin deterministik, memberikan jawaban untuk masalah komplemen).

David Richerby
sumber
4
Mungkin perlu disebutkan bahwa kita mengetahui beberapa masalah yang ada di NP dan coNP, tetapi kita tidak tahu apakah mereka ada di P atau tidak, seperti faktorisasi bilangan bulat.
user21820
@ user21820 Faktorisasi bilangan bulat bukan masalah keputusan. Primality adalah masalah keputusan dan selama bertahun-tahun diketahui memiliki NP dan co-NP . Akhirnya itu ditunjukkan dalam P juga. Saya tidak tahu apakah masih ada masalah dikenal di kedua NP dan co-NP tanpa terbukti di P .
kasperd
4
@kasperd: Ini adalah fakta yang terkenal bahwa faktorisasi bilangan bulat ketika dibuat menjadi masalah keputusan (Apakah n memiliki faktor prima kurang dari m?) ada dalam NP dan CoNP (baik contoh ya / tidak dapat diverifikasi dalam waktu polinomial melalui tes primality AKS diberi faktorisasi utama sebagai sertifikat), tetapi belum terbukti berada di P.
user21820
1
@ user21820 Ada banyak cara yang lebih sederhana dan lebih cepat untuk memverifikasi faktorisasi daripada AKS.
kasperd
@kasperd: Saya ingin tahu di sini ini. Untuk memverifikasi faktorisasi, Anda perlu misalnya faktor prima, dan untuk setiap faktor prima bukti bahwa itu prima.
gnasher729
2

"Bagaimana masalah penjual keliling diverifikasi dalam waktu polinomial?"

Baik dalam cara Anda menggambarkan, atau tidak ada yang diketahui seperti itu.

"Namun, bagaimana jika tidak ada jalan yang sesuai dengan kriteria ini?"

Dalam hal itu, untuk semua mesin NP untuk masalah keputusan, mesin akan mengembalikan tidak untuk semua sertifikat kandidat.

"Bagaimana Anda memverifikasi jawaban" tidak "tanpa memecahkan jalan TSP masalah terbaik, dan menemukan yang terbaik memiliki biaya lebih buruk daripada C?"

Yah, orang bisa menerima bukti interaktif bahwa tidak ada jalan seperti itu .

Masalah yang Anda jelaskan, TSP, tidak diketahui berada dalam coNP , jadi tidak ada yang diketahui sebagai cara "seperti NP" untuk memverifikasi bahwa tidak ada jalur seperti itu.

Juho
sumber