MAX 1 dalam 2 Algoritma SAT

8

Masalah kepuasan maksimum (Max-Sat) adalah masalah menemukan jumlah klausa maksimum yang dapat dipuaskan dalam contoh kepuasan Boolean. The tepat 1 di 2 masalah Sat bertanya, diberikan satu set klausa masing-masing dengan dua literal, ada satu set literal sehingga setiap klausul memiliki tepat satu literal dari himpunan ini.

Kompleksitas Membuat Pilihan Unik: Mendekati 1-in-k SAT oleh Guruswami dan Trevisan memberikan metode untuk mendekati Max 1 in 2 Sat. Mereka menyatakan monoton (tidak ada literasi dinegasikan) Max 1 in 2 Sat "mengakui perkiraan-e dalam waktu polinomial".

Saya ingin mencari algoritma yang tepat untuk masalah monoton Max 1 dalam 2 Sat.

graph-algorithms sat max2sat Russell Easterly
sumber

1

Monoton 1-in-Ek mengakui approximation, tetapi ini menarik hanya untuk : untuk tugas acak lebih baik. Monoton 1-in-E2 adalah MaxCut dan mengakui sebuah -approximation diberikan oleh algoritma Goemans-Williamson.

e

$e$

k \geq 4

$k\geq 4$

k < 4

$k <4$

1.138

$1.138$

Sasho Nikolov

16

Klausa 1-in-2 monoton menuntut kedua variabel memiliki nilai yang berbeda. Dengan demikian, Anda dapat memodelkan masalah sebagai masalah grafik, dengan satu simpul per variabel yang diwarnai hitam atau putih, dan tepi untuk klausa yang menunjukkan warna harus berbeda. Dengan demikian, pertanyaannya adalah membuat grafik bipartit dengan menghapus jumlah tepi minimum. Ini adalah masalah MaxCut atau Edge Bipartization. Ini NP-hard.

Untuk Bipartisasi Edge, ada algoritma yang berjalan cepat ketika beberapa tepi perlu dihapus. Saya menulis implementasi untuk masalah yang sedikit lebih umum dijelaskan di sini ( kode sumber ).

Falk Hüffner
sumber

Terima kasih. Ada cara sederhana untuk mengubah monoton Persis 1 dalam 3 SAT menjadi masalah set independen maksimal tertimbang. Jika sebuah instance dipecahkan maka grafik yang terkait dapat dibuat bipartit dengan menghapus satu sisi dari setiap klausa. Saya berharap properti 1 in 3 SAT tertentu akan membuat MaxCut lebih mudah pada jenis grafik ini. Misalnya, 1 dari 3 SAT memiliki aturan reduksi yang kuat .

Russell Easterly

14

Algoritma yang tepat untuk masalah Max Monoton 1 dalam 2 Sat (yaitu, MaxCut) berjalan lebih cepat dari (sekitar waktu) dapat ditemukan di Bab 6 dari tesis PhD saya, di sini: http: // web.stanford.edu/~rrwill/thesis.pdf $2^n$ $O(1.8^n)$

Saya tidak tahu algoritma tepat lainnya untuk masalah yang meningkatkan pencarian lengkap pada semua contoh. Untuk contoh jarang (dengan klausa ), Greg Sorkin dan rekan penulisnya memiliki sejumlah hasil algoritmik. Lihat di sini: https://sites.google.com/site/gregorysorkin/pubx $O(n)$

Ryan Williams
sumber

Terima kasih. Dimitris Achlioptas telah membuktikan klausa transisi fase ke rasio variabel untuk 1 dalam 3 SAT adalah 1/3. Dipecahkan 1 dalam 3 contoh SAT akan memiliki grafik terkait dengan rasio tepi rendah ke simpul.

Russell Easterly

@RussellEasterly Tidak juga, ini hanya berlaku untuk sebagian besar contoh yang dapat dipecahkan.

Sasho Nikolov

MAX 1 dalam 2 Algoritma SAT

Jawaban: