Memverifikasi solusi unik SAT

25

Pertimbangkan masalah berikut: diberikan formula CNF dan tugas yang memenuhi formula ini, adakah tugas lain yang memuaskan untuk formula ini?

Apa kompleksitas masalah ini? (Ini pasti di NP, tetapi juga NP-keras?)

Bagaimana jika Anda tidak diberi tugas dan Anda hanya ingin memutuskan apakah formula memiliki tugas memuaskan yang unik?

Terima kasih.

cc.complexity-theory np-hardness sat unique-solution J--
sumber
13
Masalah pertama Anda sering kali adalah pekerjaan rumah. Petunjuk: diberikan rumus F apa pun, rancang rumus F 'di mana penugasan semua-nol sepele memuaskannya, dan ada penugasan memuaskan kedua F' jika F dapat memuaskan.
Ryan Williams
1
@ Hsien-Chih Chang, kami memiliki nama Oded di halaman depan sebelum retag Anda, retagging tidak mendesak, alangkah baiknya jika namanya tetap di sana sedikit lebih lama. :)
Kaveh
1
@Kaveh: Ups, maaf. Saya kira saya entah bagaimana menganggap bahwa ia akan tetap dan terus-menerus memberikan jawaban yang lebih baik, sehingga namanya akan sering muncul di halaman utama :)
Hsien-Chih Chang 張顯 之
@ Hsien-Chih Chang, saya juga berharap begitu. :)
Kaveh

Jawaban:

27

Masalah dalam memutuskan apakah formula CNF yang diberikan memiliki penugasan yang memuaskan selain yang diberikan mudah ditunjukkan sebagai NP-lengkap dengan mengubah formula CNF untuk menambahkan satu solusi sepele. Masalah ini disebut "Masalah Solusi Lain (ASP) dari SAT" di [YS03], di mana ia digunakan untuk memberikan bukti sistematis bahwa (versi keputusan) ASP dari banyak masalah lain juga NP-complete.

Masalah memutuskan apakah formula CNF yang diberikan memiliki tugas memuaskan yang unik atau tidak (jadi Anda harus menjawab "tidak" jika rumus tidak memiliki tugas yang memuaskan atau lebih dari satu tugas yang memuaskan) adalah US -complete. AS mengandung UP dan coNP .

Referensi

[YS03] Takayuki Yato dan Takahiro Seta. Kompleksitas dan kelengkapan menemukan solusi lain dan penerapannya pada teka-teki. Transaksi IEICE tentang Dasar-Dasar Elektronik, Komunikasi dan Ilmu Komputer, E86-A (5): 1052-1060, Mei 2003.

Sunting : Versi sebelumnya (revisi 1) dari jawaban ini berisi kebingungan antara versi keputusan dan versi pencarian. Sudah diperbaiki.

Tsuyoshi Ito
sumber
6
Hanya sebuah catatan: Kelengkapan NP dari "masalah solusi lain" adalah cerita rakyat, yang dikenal jauh sebelum tahun 2003. (Mungkin ada referensi dari tahun 1970-an, tetapi buktinya sangat mudah sehingga saya meragukannya.)
Ryan Williams
@Ryan: Terima kasih atas catatannya. Saya mengedit jawaban untuk membuat hubungan dengan [YS03] lebih jelas.
Tsuyoshi Ito
22

Saya ingat Yoram Moses dan saya sendiri mempelajari masalah ini pada pertengahan 1980-an (mengingat beberapa aplikasi) dan menemukan bahwa untuk banyak masalah NPC alami masalah menemukan solusi kedua / alternatif (atau memutuskan apakah ada) adalah NPC. Kami kemudian menemukan bahwa ini diketahui, tetapi saya tidak ingat referensi, dan gagal menemukan satu (yaitu, satu sebelum pertengahan 1980-an) sekarang. Tapi saya yakin saya ingat dengan benar di atas.

Hanya komentar ke arah Ryan. Fakta bahwa teorema dapat diberikan sebagai latihan di kelas saat ini tidak membuatnya kurang menarik. Itu seharusnya diterbitkan dalam sebuah makalah yang bertuliskan judul yang memadai pada saat ditemukan ...

Oded Goldreich

Oded Goldreich
sumber
15
Hei, selamat datang! Saya sangat senang melihat Anda di sini :)
MS Dousti
12

Di sini, saya menulis kutipan dari makalah berikut:

Valiant, LG dan Vazirani, VV 1986. NP semudah mendeteksi solusi unik. Teor Komputasi. Sci. 47, 1 (November 1986), 85-93. DOI = http://dx.doi.org/10.1016/0304-3975(86)90135-0

Untuk setiap masalah NP-complete yang diketahui, jumlah solusi instansnya bervariasi pada rentang yang besar, dari nol hingga banyak secara eksponensial. Oleh karena itu wajar untuk bertanya apakah sifat tidak terpisahkan dari masalah NP-lengkap disebabkan oleh variasi yang luas ini. Kami memberikan jawaban negatif untuk pertanyaan ini menggunakan gagasan pengurangan waktu polinomial acak. Kami menunjukkan bahwa masalah membedakan antara contoh-contoh SAT yang memiliki nol atau satu solusi, atau menemukan solusi untuk contoh-contoh SAT yang memiliki solusi unik, sama sulitnya dengan SAT, dalam pengurangan acak.

Saya juga menyarankan untuk melihat makalah yang relevan:

Beigel, R., Buhrman, H., dan Fortnow, L. 1998. NP mungkin tidak semudah mendeteksi solusi unik. Dalam Prosiding Simposium ACM Tahunan ke-30 tentang teori Komputasi (Dallas, Texas, Amerika Serikat, 24-26 Mei 1998). STOC '98. ACM, New York, NY, 203-208. DOI = http://doi.acm.org/10.1145/276698.276737

MS Dousti
sumber
6

DP={(L.1∩L.2)|L.1∈NP,L.2∈CHaiNP}

Andreas Blass dan Yuri Gurevich, Tentang masalah kepuasan yang unik,

Mohammad Al-Turkistany
sumber
1
Poin kecil: Masalah kedua bukanlah masalah janji.
Tsuyoshi Ito
1
Saya sudah menyadarinya dan memperbaikinya, tapi terima kasih sudah menemukannya!
Tsuyoshi Ito
6
Ngomong-ngomong, saya tidak menyalin apa pun dari jawaban Anda, jadi saya tidak tahu apa yang dimaksud dengan komentar Anda berikut: "Ketika Anda menyalin dari jawaban lain, tolong tunjukkan itu." di MathOverflow ( mathoverflow.net/questions/31251/… ), tapi saya tidak berpikir Anda merujuk ini.
Tsuyoshi Ito