Apakah ada algoritma yang kadang-kadang efisien untuk menyelesaikan #SAT?

Biarkan menjadi rumus boolean yang terdiri dari operator AND, OR, dan NOT yang biasa dan beberapa variabel. Saya ingin menghitung jumlah memuaskan tugas untuk . Yaitu, saya ingin menemukan jumlah penugasan yang berbeda dari nilai kebenaran ke variabel yang mengasumsikan nilai sebenarnya. Misalnya, rumus memiliki tiga penugasan yang memuaskan; memiliki empat. Ini adalah masalah #SAT . $B$ $B$ $B$ $B$ $a\lor b$ $(a\lor b)\land(c\lor\lnot b)$

Jelas solusi yang efisien untuk masalah ini akan menyiratkan solusi yang efisien untuk SAT, yang tidak mungkin, dan pada kenyataannya masalah ini adalah # P-selesai, dan mungkin sangat sulit daripada SAT. Jadi saya tidak mengharapkan solusi yang dijamin efisien.

Tetapi diketahui bahwa ada beberapa contoh yang sangat sulit dari SAT itu sendiri. (Lihat misalnya Cheeseman 1991, "Di mana masalah yang benar - benar sulit" .) Pencarian pemangkasan biasa, meskipun eksponensial dalam kasus terburuk, dapat menyelesaikan banyak contoh secara efisien; metode resolusi, meskipun eksponensial dalam kasus terburuk, bahkan lebih efisien dalam praktiknya.

Pertanyaanku adalah:

Apakah ada algoritma yang diketahui yang dapat dengan cepat menghitung jumlah penugasan yang memuaskan dari formula boolean yang khas, bahkan jika algoritma tersebut membutuhkan waktu eksponensial dalam contoh umum? Apakah ada yang terasa lebih baik daripada menghitung setiap tugas yang mungkin?

complexity-theory reference-request satisfiability Mark Dominus
sumber

Saya mencoba menambahkan tag untuk kelengkapan # p, tetapi perangkat lunak Stack Exchange tidak menyukai tanda #.

Mark Dominus

Saya akan berhati-hati dengan mengklaim bahwa "ada beberapa contoh yang sangat sulit dari SAT itu sendiri". Saya percaya makalah yang Anda tautkan benar-benar berbicara tentang -SAT acak . Lebih lanjut, fenomena transisi fase hanya berlaku untuk instance acak. Ada banyak contoh SAT, kerajinan tangan, industri dll.

k

$k$

Juho

Terima kasih. Apakah Anda pikir ini cenderung membuat pertanyaan saya kurang jelas? Apakah Anda mengerti apa yang saya minta?

Mark Dominus

Jelas bagi saya. Hanya penting untuk mengingat contoh apa yang memperlihatkan transisi fase :)

Juho

Jawaban:

Menghitung dalam kasus umum

Masalah yang Anda minati dikenal sebagai #SAT, atau penghitungan model. Dalam arti tertentu, ini adalah masalah # P-complete klasik. Menghitung model itu sulit, bahkan untuk -SAT! Tidak mengherankan, metode yang tepat hanya dapat menangani contoh dengan sekitar ratusan variabel. Metode perkiraan ada juga, dan mereka mungkin bisa menangani contoh dengan sekitar 1000 variabel. $2$

Metode penghitungan yang tepat sering didasarkan pada pencarian lengkap gaya DPLL atau semacam kompilasi pengetahuan. Metode perkiraan biasanya dikategorikan sebagai metode yang memberikan perkiraan cepat tanpa jaminan dan metode yang memberikan batas yang lebih rendah atau lebih tinggi dengan jaminan kebenaran. Ada juga metode lain yang mungkin tidak sesuai dengan kategori, seperti menemukan pintu belakang, atau metode yang bersikeras pada sifat struktural tertentu untuk berpegang pada formula (atau grafik kendala mereka).

Ada implementasi praktis di luar sana. Beberapa penghitung model yang tepat adalah CDP, Relsat, Cachet, sharpSAT, dan c2d. Jenis teknik utama yang digunakan oleh pemecah yang tepat adalah jumlah parsial, analisis komponen (dari grafik kendala underying), rumus dan caching komponen, dan penalaran cerdas pada setiap node. Metode lain berdasarkan kompilasi pengetahuan mengubah input formula CNF ke bentuk logis lain. Dari formulir ini, jumlah model dapat disimpulkan dengan mudah (waktu polinomial dalam ukuran formula yang baru diproduksi). Sebagai contoh, seseorang dapat mengubah formula menjadi diagram keputusan biner (BDD). Seseorang kemudian dapat melintasi BDD dari daun "1" kembali ke root. Atau untuk contoh lain, c2d menggunakan kompiler yang mengubah rumus CNF menjadi bentuk normal negasi dekomposisi deterministik (d-DNNF).

Jika instance Anda menjadi lebih besar atau Anda tidak peduli dengan ketepatannya, metode perkiraan juga ada. Dengan metode perkiraan, kami peduli dan mempertimbangkan kualitas estimasi dan kepercayaan kebenaran yang terkait dengan estimasi yang dilaporkan oleh algoritma kami. Satu pendekatan oleh Wei dan Selman [2] menggunakan MCMC sampling untuk menghitung perkiraan jumlah model sebenarnya untuk formula input. Metode ini didasarkan pada fakta bahwa jika seseorang dapat mengambil sampel (hampir) secara seragam dari himpunan solusi rumus , maka seseorang dapat menghitung perkiraan yang baik dari jumlah solusi . $\phi$ $\phi$

Gogate dan Dechter [3] menggunakan teknik penghitungan model yang dikenal sebagai SampleMinisat. Ini didasarkan pada pengambilan sampel dari ruang pencarian bebas-mundur dari formula boolean. Teknik ini dibangun berdasarkan gagasan pentingnya pengambilan sampel ulang, menggunakan solver SAT berbasis DPLL untuk membangun ruang pencarian bebas-lacak. Ini mungkin dilakukan sepenuhnya atau hingga perkiraan. Pengambilan sampel untuk perkiraan dengan jaminan juga dimungkinkan. Membangun di atas [2], Gomes et al. [4] menunjukkan bahwa menggunakan pengambilan sampel dengan strategi acak yang dimodifikasi, seseorang dapat memperoleh batas bawah yang dapat dibuktikan pada jumlah total model dengan jaminan kebenaran probabilistik yang tinggi.

Ada juga pekerjaan yang dibangun berdasarkan propagasi keyakinan (BP). Lihat Kroc et al. [5] dan BPCount yang mereka perkenalkan. Dalam makalah yang sama, penulis memberikan metode kedua yang disebut MiniCount, untuk memberikan batas atas pada jumlah model. Ada juga kerangka kerja statistik yang memungkinkan seseorang untuk menghitung batas atas berdasarkan asumsi statistik tertentu.

Algoritma untuk # 2-SAT dan # 3-SAT

Jika Anda membatasi perhatian Anda ke # 2-SAT atau # 3-SAT, ada algoritma yang berjalan di dan untuk masing-masing masalah ini [1]. Ada sedikit peningkatan untuk algoritma ini. Sebagai contoh, Kutzkov [6] meningkat pada batas atas [1] untuk # 3-SAT dengan algoritma yang berjalan dalam waktu . $O(1.3247^n)$ $O(1.6894^n)$ $O(1.6423^n)$

Seperti dalam sifat masalah, jika Anda ingin menyelesaikan contoh dalam praktik, banyak tergantung pada ukuran dan struktur contoh Anda. Semakin banyak Anda tahu, semakin Anda mampu memilih metode yang tepat.

[1] Vilhelm Dahllöf, Peter Jonsson, dan Magnus Wahlström. Menghitung Tugas yang Memuaskan dalam 2-SAT dan 3-SAT. Dalam Prosiding Konferensi Komputasi dan Kombinatorik Internasional Tahunan ke-8 (COCOON-2002), 535-543, 2002.

[2] W. Wei, dan B. Selman. Pendekatan Baru Menghitung Model. Dalam Prosiding SAT05: Konferensi Internasional ke-8 tentang Teori dan Aplikasi Pengujian Kepuasan, volume 3569 dari Catatan Kuliah dalam Ilmu Komputer, 324-339, 2005.

[3] R. Gogate, dan R. Dechter. Perkiraan Menghitung dengan Sampling Ruang Pencarian Backtrack-gratis. Dalam Prosiding AAAI-07: Konferensi Nasional ke 22 tentang Kecerdasan Buatan, 198–203, Vancouver, 2007.

[4] CP Gomes, J. Hoffmann, A. Sabharwal, dan B. Selman. Dari Sampling ke Penghitungan Model. Dalam Prosiding IJCAI-07: Konferensi Bersama Internasional ke-20 tentang Kecerdasan Buatan, 2293–2299, 2007.

[5] L. Kroc, A. Sabharwal, dan B. Selman. Memanfaatkan Propagasi Keyakinan, Pencarian Mundur, dan Statistik untuk Penghitungan Model. Dalam CPAIOR-08: Konferensi Internasional ke-5 tentang Integrasi Teknik AI dan OR dalam Pemrograman Kendala, volume 5015 dari Catatan Kuliah dalam Ilmu Komputer, 127–141, 2008.

[6] K. Kutzkov. Batas atas baru untuk masalah # 3-SAT. Pemrosesan Informasi Surat 105 (1), 1-5, 2007.

Juho
sumber

Selain makalah-makalah yang disebutkan oleh Juho, berikut adalah beberapa makalah lain yang menjelaskan pekerjaan tentang topik ini, terutama tentang perkiraan jumlah solusi:

Penghitungan Model . Carla P. Gomes, Ashish Sabharwal, Buku Panduan Bart Selman of Satisfiability, IOS Press. Editor: Armin Biere, Marijn Heule, Hans van Maaren, dan Toby Walsh. Bab 20, hlm 633-654, 2009.
- Ini memiliki ikhtisar yang bagus tentang topik dan pengantar sejumlah teknik.
Sampling Near-Uniform Ruang Kombinatorial Menggunakan Kendala XOR . Carla P. Gomes, Ashish Sabharwal, Bart Selman. NIPS-06. Konferensi Tahunan ke-20 tentang Sistem Pemrosesan Informasi Saraf Tiruan, hal. 481-488, Vancouver, BC, Kanada, Desember 2006.
XOR Pendek untuk Penghitungan Model: Dari Teori ke Praktik . Carla P. Gomes, Joerg Hoffmann, Ashish Sabharwal, Bart Selman SAT-07. Konferensi Internasional ke-10 tentang Teori dan Aplikasi Pengujian Kepuasan, volume LNCS 4501, hlm 100-106, Lisbon, Portugal, Mei 2007.
Memanfaatkan Propagasi Keyakinan, Pencarian Mundur, dan Statistik untuk Penghitungan Model . Lukas Kroc, Ashish Sabharwal, Bart Selman ANOR-2011. Annals of Operations Research, volume 184, nomor 1, hlm 209-231, 2011.
Heuristik untuk Penghitungan Model Cepat Exact . Tian Sang, Paul Beame, dan Henry Kautz. Teori dan Aplikasi Pengujian Kepuasan (SAT 2005), hal 226-240.

DW
sumber