Masalah SAT mana yang mudah?

27

Apa itu "daerah mudah" untuk kepuasan? Dengan kata lain, kondisi yang cukup untuk beberapa pemecah SAT untuk dapat menemukan tugas yang memuaskan, dengan asumsi itu ada.

Salah satu contoh adalah ketika masing-masing klausa berbagi variabel dengan beberapa klausa lain, karena bukti LLL yang konstruktif , apakah ada hasil lain di sepanjang garis itu?

Ada banyak literatur tentang wilayah yang mudah untuk Propagasi Keyakinan, apakah ada sesuatu di sepanjang garis itu untuk kepuasan?

cc.complexity-theory sat Yaroslav Bulatov
sumber
2
apakah Anda juga tertarik dengan transisi fase SAT acak?
Suresh Venkat
Seperti apa kondisi yang cukup itu? Peter Shor menyebutkan dalam posting lain bahwa instance SAT perlu memiliki "struktur acak" untuk membuat rasio klausa dengan variabel yang relevan. Saya ingin tahu apakah ini adalah sesuatu yang dapat dikodekan ke dalam kondisi yang cukup
Yaroslav Bulatov

Jawaban:

33

Saya kira Anda tahu hasil klasik Schaefer dari STOC'78, tetapi untuk berjaga-jaga.

10.1145 / 800133.804350

Schaefer membuktikan bahwa jika SAT parametris dengan seperangkat hubungan yang diizinkan dalam contoh apa pun, maka hanya ada 6 kasus yang dapat ditelusuri: 2-SAT (yaitu setiap klausa adalah biner), Horn-SAT, dual-Horn-SAT, affine-SAT ( solusi untuk persamaan linear dalam GF (2)), 0-valid (relasi dipenuhi oleh semua-0 penugasan) dan 1-valid (relasi dipenuhi oleh semua-1 penugasan).

Standa Zivny
sumber
3
Ada makalah yang lebih baru yang memperbaiki hasil ini: Kompleksitas masalah kepuasan: "Teorema pemurnian Schaefer" Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor dan Heribert Vollmer
Vinicius dos Santos
1
Terima kasih, ini doi: dx.doi.org/10.1016/j.jcss.2008.11.001
Standa Zivny
Perhatikan bahwa ini adalah masalah kepuasan kendala dan bukan SAT (meskipun mereka dapat ditulis ulang sebagai instance SAT, tetapi secara teknis, SAT berarti CSP dengan ATAU predikat).
MCH
14

Saya tidak yakin apakah ini yang Anda cari tetapi ada literatur yang cukup besar tentang transisi fase 3-SAT.

Monasson, Zecchina, Kirkpatrcik, Selman dan Troyansky memiliki makalah yang membahas tentang fase transisi k-SAT acak. Mereka menggunakan parameterisasi rasio klausa terhadap variabel. Untuk 3-SAT acak, mereka menemukan secara numerik bahwa titik transisi adalah sekitar 4,3. Di atas titik ini contoh 3-SAT acak lebih dibatasi dan hampir pasti tidak dapat diverifikasi dan di bawah ini masalah berada di bawah dibatasi dan memuaskan (dengan probabilitas tinggi). Mertens, Mezard dan Zecchina menggunakan prosedur metode rongga untuk memperkirakan titik transisi fase ke tingkat akurasi yang lebih tinggi.

Jauh dari titik kritis, algoritma "bisu" bekerja dengan baik untuk instance yang memuaskan (walk sat, dll.). Dari apa yang saya mengerti, waktu menjalankan pemecah deterministik tumbuh secara eksponensial pada atau dekat fase transisi (lihat di sini untuk diskusi lebih lanjut?).

Sepupu dekat propagasi kepercayaan, Braunstein, Mezard dan Zecchina telah memperkenalkan propagasi survei yang dilaporkan memecahkan contoh 3-SAT yang memuaskan dalam jutaan variabel, bahkan sangat dekat dengan fase transisi. Mezard memiliki kuliah di sini tentang kacamata spin (teori yang telah ia gunakan dalam analisis transisi fase NP-Lengkap acak) dan Maneva memiliki kuliah di sini tentang propagasi survei.

Dari arah lain, sepertinya pemecah terbaik kita mengambil jumlah waktu yang eksponensial untuk membuktikan ketidakpuasan. Lihat di sini , di sini dan di sini untuk bukti / diskusi tentang sifat eksponensial dari beberapa metode umum dalam membuktikan ketidakpuasan (prosedur Davis-Putnam dan metode penyelesaian).

Kita harus sangat berhati-hati tentang klaim 'kemudahan' atau 'kekerasan' untuk masalah NP-Complete acak. Memiliki masalah NP-Complete menampilkan transisi fase tidak memberikan jaminan di mana masalah sulit berada atau apakah ada. Misalnya, masalah Siklus Hamiltoniain pada grafik acak Erdos-Renyi terbukti mudah bahkan di atau dekat titik transisi kritis. Masalah Partisi Angka tampaknya tidak memiliki algoritma apa pun yang menyelesaikannya dengan baik ke dalam rentang probabilitas 1 atau 0, apalagi di dekat ambang kritis. Dari apa yang saya pahami, masalah 3-SAT acak memiliki algoritma yang bekerja dengan baik untuk contoh yang memuaskan hampir pada atau di bawah ambang kritis (propagasi survei, walk sat, dll.) Tetapi tidak ada algoritma efisien di atas ambang kritis untuk membuktikan ketidakpuasan.

pengguna834
sumber
Saya bertanya-tanya apakah salah satu dari "k-SAT" acak itu menghasilkan transfer ke instance SAT kehidupan nyata, dengan kata lain jika rasio klausa terhadap variabel masih merupakan indikator kekerasan yang bermanfaat
Yaroslav Bulatov
1
@Yaroslav, dari pengalaman saya, tidak. Banyak masalah dunia nyata (bahkan reduksi) memiliki (atau memperkenalkan) begitu banyak struktur sehingga dapat menghancurkan keacakan yang telah dioptimalkan untuk banyak pemecah masalah. Sepertinya pada titik tertentu kita mungkin bisa menjelaskan struktur itu entah bagaimana dan hanya bisa fokus pada bagian keacakan (atau 'esensi' dari masalah acak) tetapi saya tidak melihat cara umum untuk melakukan itu atau apakah saya benar-benar mengetahui contoh yang menggunakan strategi itu.
user834
R(F)Fr∈[0,1]F
5

Ada banyak kondisi yang cukup. Dalam beberapa hal, banyak CS teoritis telah dikhususkan untuk pengumpulan kondisi ini - traktabilitas parameter tetap, 2-SAT, acak 3-SAT dari kepadatan yang berbeda, dll.

Peter Boothe
sumber
2
Itu benar, orang dapat mengambil masalah X yang mudah dipecahkan dan mengatakan bahwa "rumus apa pun yang sesuai dengan masalah X mudah". Saya kira saya sedang mencari kondisi yang cukup yang lebih efisien dalam meringkas wilayah yang mudah daripada "semua masalah yang diketahui ada di P", lebih seperti apa yang dilakukan oleh Lovasz Local Lemma yang konstruktif
Yaroslav Bulatov
3

sejauh ini tidak banyak pengakuan konsep ini dalam literatur, tetapi grafik klausa dari masalah SAT (grafik dengan satu node per klausa, dan node terhubung jika klausa berbagi variabel), serta grafik terkait lainnya representasi SAT, tampaknya memiliki banyak petunjuk dasar tentang seberapa keras contoh akan rata-rata.

grafik klausa dapat dianalisis melalui semua jenis grafik teorema algoritma, merupakan ukuran "struktur" yang tampaknya alami dan dengan koneksi yang kuat untuk mengukur / memperkirakan kekerasan, dan tampaknya penelitian dalam struktur ini dan implikasinya masih sangat awal. tahapan. tidak dapat dibayangkan bahwa penelitian titik transisi, a / cara tradisional dan dipelajari dengan baik untuk mendekati pertanyaan ini, pada akhirnya mungkin dijembatani ke dalam struktur grafik klausa ini (sampai taraf tertentu sudah ada). dengan kata lain titik transisi dalam SAT dapat dilihat "karena" struktur grafik klausa.

di sini adalah salah satu referensi yang sangat baik di sepanjang baris ini, tesis Phd oleh Herwig, ada banyak lainnya

[1] Mengurai masalah kepuasan atau Menggunakan grafik untuk mendapatkan wawasan yang lebih baik tentang masalah kepuasan , Herwig 2006 (83pp)

ay
sumber
ini adalah grafik ketergantungan ketika menerapkan lemas dan varian lokal lovasz untuk kepuasan. dalam arti itu, grafik klausa telah banyak dilihat . Shearer mencirikan grafik yang dimiliki oleh lemma lokal, dan Kolipaka dan Szegedy telah menjadikan hasil Schaefer konstruktif. Ketika Anda tidak tahu banyak, tolong jangan menyimpulkan bahwa tidak ada yang tahu!
Sasho Nikolov
perincian shaefers ke dalam beberapa kelas yang dapat ditelusuri disebutkan dalam jawaban oleh Zivny tetapi analisis grafik klausa ini relatif lebih baru, lebih dalam dan lebih bernuansa, dan lebih banyak lagi dengan citarasa empiris. Adapun kutipan yang Anda sebutkan, sepertinya tidak sering disebutkan dalam SAT hardness papers / penelitian ... ada beberapa / paralel baris yang saling terkait penyelidikan ...
vzn
Schaefer salah ketik, maksudku Shearer. LLL dan variannya adalah alat utama dalam membatasi contoh keras k-SAT, pencarian google akan mengungkapkan banyak referensi. Teorema Shearer menunjukkan grafik klausa mana yang menjamin bahwa setiap instance SAT dengan grafik tersebut harus memuaskan. Lihatlah survei ini untuk koneksi terperinci ke ambang kekerasan, kesulitan membangun mesin virtual
Sasho Nikolov
1
sebuah pemikiran umum: setiap kali Anda mengatakan sesuatu adalah terra incognita, ada kemungkinan besar itu terra incognita bagi Anda . dalam hal apa pun komentar semacam ini tidak berguna kecuali Anda adalah seorang pakar yang telah mapan dan dipublikasikan di wilayah tersebut. akan lebih baik jika Anda membatasi jawaban Anda pada apa yang Anda ketahui dan meninggalkan komentar tentang apa yang menurut Anda tidak ada yang tahu.
Sasho Nikolov
1
LLL adalah salah satu alat untuk menganalisis SAT, ditemukan pada tahun 1975 dengan mungkin beberapa penyempurnaan sejak saat itu. itu resep untuk contoh mudah atau sulit yang cukup tetapi tidak perlu . pendekatan lain sejak saat itu memang ada yang semakin mengisi kesenjangan dalam cara-cara baru yaitu memperluas dan memotongnya. Anda harus membingungkan jawaban ini dengan sesuatu yang lain, tidak ada penggunaan istilah "terra incognita" dalam pertanyaan di atas. & sarankan Anda membatasi diri pada jawaban tertulis yang sebenarnya & tidak berspekulasi tentang apa yang orang lain tahu atau tidak tahu =)
vzn
1

Sangat mudah untuk memindahkan semua instance di dekat titik "transisi" ke jauh dari titik "transisi" seperti yang diinginkan. Gerakan ini melibatkan upaya waktu / ruang polinomial.

Jika contoh yang jauh dari titik "transisi" lebih mudah untuk dipecahkan, maka yang dekat dengan titik transisi harus sama mudahnya untuk diselesaikan. (Transformasi polinomial dan semuanya.)

GHR
sumber
dapatkah Anda menguraikan, atau apakah Anda memiliki referensi untuk ini?
vzn
1

κ

ia menemukan sebuah jelas fraktal diri kemiripan struktur contoh keras wrt constrainedess parameter seperti itu sebagai DP (LL) solver selama pencarian cenderung untuk menemukan subproblem dengan constrainedness kritis sama tidak peduli yang variabel yang dipilih di sebelah cabang di. ada beberapa analisis lebih lanjut dari struktur fraktal dalam kasus SAT (seperti dimensi Hausdorff dari rumus SAT & koneksi ke kekerasan) dalam misalnya [2,3]

jalur penyelidikan lain yang agak saling terkait di sini adalah hubungan grafik dunia kecil dengan struktur SAT (keras) misalnya [4,5]

=?

[1] Tepian pisau kendala oleh Toby Walsh 1998

[2] SEDERHANA DIRI DARI EKSPRESI BOOLEAN YANG MEMUASKAN YANG TERPASANG DALAM KETENTUAN SISTEM FUNGSI ITERASI LANGSUNG GAMBAR oleh Ni dan Wen

[3] Visualisasi Struktur Internal Instance SAT (Laporan Awal) Sinz

[4] Cari di dunia kecil oleh Walsh 1999

[5] Pemodelan masalah SAT yang lebih realistis oleh Slater 2002

ay
sumber
3
Ngomong-ngomong, ini DPLL, bukan DP (LL). Juga, ada pekerjaan yang jauh lebih baru pada transisi fase dalam SAT (lihat karya Achlioptas, misalnya).
Vijay D
ada algoritma DP yang mendahului DPLL yang memiliki perilaku serupa. jawaban lain oleh user834 terutama menyebutkan penelitian titik transisi SAT dengan banyak referensi tetapi jawaban ini menekankan sudut yang berbeda (tetapi saling terkait)
vzn
1
Saya mengetahui algoritma ini. Saya hanya menunjukkan konvensi tipografi standar, yaitu menulis DP, atau DPLL, atau DPLL (T), atau DPLL (Gabung), untuk case first order-free quantifier. Tidak ada yang menulis DP (LL) dan itu menambah kebingungan dengan DPLL (T) dan DPLL (Gabung)
Vijay D
DP (LL) adalah apa yang dimaksud dengan DP + DPLL
vzn