Hitung semua solusi dari masalah SAT

11

Semua pemecah #SAT yang saya tahu, misalnya RelSat, C2D, hanya mengembalikan jumlah instance yang memuaskan. Tapi saya ingin tahu masing-masing contoh itu?

Apakah ada solver #SAT atau bagaimana saya harus memodifikasi solver #SAT yang tersedia untuk melakukan ini?

Terima kasih.

lo.logic sat software qsp
sumber
7
Ini sering disebut "semua-solusi SAT solver", tetapi tampaknya tidak tersedia di pasaran. Referensi saya dapat menemukan pembicaraan tentang modifikasi untuk MiniSAT dan pemecah masalah lainnya, biasanya dengan menambahkan klausa pemblokiran untuk mengecualikan solusi ketika ditemukan. Di sisi lain, sebagian besar pemecah kendala mendukung pembuatan semua solusi sebagai standar.
András Salamon
satu pendekatan adalah konversi CNF → DNF yang memiliki banyak literatur
vzn

Jawaban:

13

Anda mencari solusi SAT-SAT atau semua solusi SAT. Ini adalah masalah yang berbeda dari #SAT. Anda tidak perlu menghitung semua solusi untuk menghitungnya.

Saya tidak tahu alat yang memecahkan masalah Anda karena orang menambahkan algoritma ini di atas pemecah SAT yang ada tetapi jarang melepaskan ekstensi ini. Dua makalah yang seharusnya membantu Anda dalam memodifikasi pemecah CDCL untuk menerapkan ALL-SAT ada di bawah ini.

Pemecah SAT Semua Solusi yang Efisien Memori dan Penerapannya untuk Reachability , O. Grumberg, A. Schuster, A. Yadgar, FMCAD 2004

Berikut ini adalah artikel terbaru yang diposting di arXiv.

Memperluas Solver SAT Modern untuk Menghitung Semua Model , Said Jabbour, Lakhdar Sais, Yakoub Salhi, 2013

Anda dapat mencoba menghubungi penulis ini untuk penerapannya.

Vijay D
sumber
Untuk makalah kedua Anda hanya perlu mengklik versi pertama v1 untuk melihatnya.
Tayfun Bayar
Makalah baru-baru ini tampaknya terkait: homes.cs.washington.edu/~sudeepa/UAI2013-ModelCounting.pdf
Kaveh
1
@ Kaveh, saya percaya OP meminta solver ALLSAT atau cara untuk mengubah solver #SAT menjadi solver ALLSAT. Ini adalah makalah tentang batas bawah untuk #SAT. Saya tidak yakin ini membantu OP.
Vijay D
2

Saya menemukan makalah yang lebih baru (2014) tentang All-SAT di sebuah konferensi VLSI, jadi pasti diarahkan ke sisi praktis (yang tampaknya selaras dengan pertanyaan OP di sini, meskipun kurang begitu dengan cstheory.SE secara umum):

  • "Semua-SAT menggunakan Minimal Blocking Clauses" oleh Yinlei Yu, Pramod Subramanyan, Nestan Tsiskaridze, Sharad Malik, VLSI Design 2014. doi: 10.1109 / VLSID.2014.22 .

Bagi mereka yang tidak berlangganan IEEE, ada salinan gratis di halaman web Princeton Subramanyan . (Dia menggunakan layanan berbagi file untuk menyimpan / mendistribusikan salinan makalahnya dan saya tidak yakin seberapa stabil URL itu, karenanya tautan bundaran ini.)

Inti dari makalah ini adalah:

Kontribusi kami, algoritma Non-Disjoint-Dec, menghasilkan klausa pemblokiran yang sangat singkat yang tidak mengandung variabel tersirat dalam pemecah. Perhatikan bahwa biasanya mayoritas variabel dalam minterm yang memuaskan tersirat. Klausa pemblokiran pendek sangat bermanfaat untuk kinerja pemecah seperti yang ditunjukkan oleh evaluasi.

Implementasi mereka dibangun di atas MiniSat. Kode sumber untuk ekstensi mereka tampaknya tidak tersedia untuk umum. Sayangnya ini tampaknya menjadi kebiasaan di bidang All-SAT, jadi makalah di daerah ini yang berisi hasil eksperimen hanya menyiapkan beberapa algoritma jerami-manusia lebih atau kurang sederhana untuk mengalahkan dan jarang dapat langsung dibandingkan (dalam hal eksperimental hasil) dengan algoritma lain yang dipublikasikan untuk All-SAT. Makalah oleh Jabbour et al. disebutkan oleh Vijay D juga dari jenis ini.

Karena saya tidak melihatnya disebutkan dalam jawaban lain (tetapi hanya dalam komentar András Salamon), techinique blocking [agak populer] diperkenalkan pada:

Mendesis
sumber