Masalah NP dengan solusi unik

8

Apakah ada kelas masalah NP yang memiliki satu solusi unik? Saya bertanya itu, karena ketika saya belajar kriptografi saya membaca tentang ransel dan saya menemukan ide yang sangat menarik.

complexity-theory decision-problem np cryptography Marco
sumber
Tampaknya Anda tidak yakin dengan terminologi Anda; Masalah NP dapat dengan mudah sewenang-wenang, dan biasanya masalah keputusan (yang selalu memiliki solusi unik, ya atau tidak); baca lebih lanjut di pertanyaan referensi kami . Saya berasumsi Anda ingin masalah sulit NPO dengan solusi unik?
Raphael
Ya, maksud saya NP lengkap atau NP keras, atau apa pun yang tidak ada dalam P ... Maaf dan terima kasih untuk menunjukkan
Marco
Kami tidak tahu apakah masalah NP-complete tidak ada di P ...
Raphael

Jawaban:

12

Ya, kelas ini disebut UP (U singkatan "tidak ambigu"). David menunjukkan dalam komentar bahwa jawaban lain adalah AS .

UP: Jika x∈L, maka tepat ada satu "bukti" ("saksi", "sertifikat", "jalur penerimaan"). Jikax∉L, ada persis nol "bukti".

AS: Jika x∈L, maka tepat ada satu "bukti". Jikax∉L, mungkin ada nol bukti, atau 2+ bukti, selama tidak ada satu pun.

usul
sumber
2
Atau AS, kelas kompleksitas yang berbeda. (Untuk mesin UP, selalu ada paling banyak satu jalur penerimaan, untuk AS bisa ada lebih dari satu tetapi mereka hanya menerima jika ada persis satu.)