Masalah NP-Complete yang mengakui algoritma yang efisien di bawah janji solusi yang unik

Saya baru-baru ini membaca makalah yang sangat bagus oleh Valiant dan Vazirani yang menunjukkan bahwa jika , maka tidak akan ada algoritma yang efisien untuk menyelesaikan SAT bahkan di bawah janji bahwa itu tidak memuaskan atau memiliki solusi yang unik. Dengan demikian menunjukkan bahwa SAT tidak mengakui algoritma yang efisien bahkan di bawah janji ada paling banyak satu solusi. $\mathbf{NP \neq RP}$

Melalui reduksi parsimoni (pengurangan yang mempertahankan jumlah solusi), mudah untuk melihat bahwa sebagian besar masalah NP-complete (saya bisa memikirkan) juga tidak mengakui algoritma yang efisien bahkan di bawah janji ada paling banyak satu solusi (kecuali ). Contohnya adalah VERTEX-COVER, 3-SAT, MAX-CUT, 3D-MATCHING. $\mathbf{NP = RP}$

Oleh karena itu saya bertanya-tanya apakah ada masalah NP-lengkap yang diketahui mengakui algoritma poli-waktu di bawah janji keunikan.

np-hardness np-complete unique-solution promise-problems setan
sumber

Ini bukan jawaban yang sangat baik, tetapi ada banyak masalah NP-lengkap yang instansnya selalu nol atau lebih dari satu solusi. Perhatikan grafik 3-warna misalnya; solusi datang dalam kelompok 6 karena Anda selalu dapat mengubah warna. Masalah seperti itu memiliki algoritma waktu polinomial dengan janji paling banyak satu solusi. Secara khusus, jika ada paling banyak satu 3-pewarnaan maka tidak mungkin ada, sehingga algoritma hanya bisa menolak.

Mikhail Rudoy

Masalah siklus Hamilton mengakui algoritma waktu lebih cepat (tapi masih eksponensial) di bawah promiss uniqness. Itu tidak secara langsung menjawab pertanyaan Anda, karena itu bukan jumlahnya banyak, tetapi setidaknya ini adalah masalah dengan perilaku yang berbeda daripada SAT

ivmihajlin

Seperti dalam komentar Mikhail Rudoy, pengujian untuk keberadaan siklus Hamilton dalam grafik 3-reguler adalah sepele dengan asumsi keunikan. Setiap sisi berpartisipasi dalam jumlah siklus Hamilton yang genap, sehingga tidak akan pernah ada satu pun.

David Eppstein

Masalah NP-Complete yang mengakui algoritma yang efisien di bawah janji solusi yang unik

Jawaban: