Apakah ada penelitian tentang -SAT di atas ambang batas kepuasan?

25

Karakteristik yang terkenal dari instance -SAT adalah rasio jumlah klausa atas jumlah variabel , yaitu, hasil bagi . Untuk setiap , ada nilai ambang st \ untuk , sebagian besar instance memuaskan, dan untuk kebanyakan instance tidak memuaskan. Ada banyak penelitian yang dilakukan untuk masalah di mana , dan untuk masalah dengan cukup kecil , $k$ $m$ $n$ $\rho = m/n$ $k$ $\alpha$ $\rho \ll \alpha$ $\rho \gg \alpha$ $\rho \ll \alpha$ $\rho$ $k$ -SAT menjadi dipecahkan dalam waktu polinomial. Lihat, misalnya, artikel survei Dimitris Achlioptas dari Handbook of Satisfiability ( PDF ).

Saya bertanya-tanya apakah ada pekerjaan yang telah dilakukan ke arah lain (di mana ), misalnya, jika kita dapat mengubah masalah dari CNF ke DNF dalam kasus ini untuk menyelesaikannya dengan cepat. $\rho \gg \alpha$

Jadi, pada dasarnya, Apa yang diketahui tentang SAT di mana ? $\rho = m/n \gg \alpha$

cc.complexity-theory sat random-k-sat phase-transition Matt Groff
sumber

10

Perlu dicatat bahwa adalah fungsi dari .

α

$\alpha$

k

$k$

Huck Bennett

mungkinkah ada beberapa transformasi yang menunjukkan semacam simetri antara kedua daerah di kedua "sisi" dari titik transisi? tampaknya masuk akal. Lagi pula pertanyaannya agak luas dalam arti ada banyak studi empiris / teoritis dari titik transisi yang tidak terlalu fokus pada satu "sisi" atau yang lain ...

vzn

26

Ya, sudah ada. Moshe Vardi baru-baru ini memberikan ceramah survei di Yayasan Teoritis BIRS dari lokakarya Pemecahan SAT Terapan :

Moshe Vardi, Transisi fase dan kompleksitas komputasi , 2014.

(Moshe menyajikan grafik percobaan mereka sedikit setelah menit 14:30 dalam ceramahnya yang ditautkan di atas.)

Mari menunjukkan rasio klausa. Karena nilai meningkat melampaui ambang batas, masalahnya menjadi lebih mudah untuk pemecah SAT yang ada, tetapi tidak semudah sebelum mencapai ambang batas. Ada peningkatan kesulitan yang sangat tajam saat kami mendekati ambang batas dari bawah. Setelah ambang batas masalah menjadi lebih mudah dibandingkan dengan ambang batas tetapi penurunan tingkat kesulitannya tidak terlalu tajam. $\rho$ $\rho$

Misalkan menunjukkan kesulitan dari masalah wrt to (dalam percobaan mereka adalah rata-rata waktu berjalan GRASP pada instance 3SAT acak dengan rasio klausa ). Moshe menyarankan agar berubah sebagai berikut: $T_\rho(n)$ $n$ $T_\rho(n)$ $\rho$ $T_\rho(n)$

$\rho \ll$ ambangnya: adalah polinomial dalam , $T_\rho(n)$ $n$
$\rho$ ada di dekat ambang batas: bersifat eksponensial dalam , $T_\rho(n)$ $n$
$\rho \gg$ ambang batas: tetap eksponensial dalam tetapi eksponen menurun dengan meningkatnya . $T_\rho(n)$ $n$ $\rho$

Kaveh
sumber

1

Perlu dicatat bahwa hasil di atas adalah hasil percobaan (dari sekitar 2000) menggunakan SAT-solver (GRASP) tertentu. Tetapi, secara teori, diketahui bahwa untuk (katakanlah, ) yang cukup besar, bahkan resolusi memiliki bantahan kecil tentang ketidakpuasan. Dan, seperti yang ditulis Jan Johannsem sebelumnya, menyangkal 3-SAT itu mudah (dalam kasus rata-rata) sudah ketika .

ρ

$\rho$

Ω (n)

$\Omega(n)$

ρ = Ω (\sqrt{n})

$\rho=\Omega(\sqrt{n})$

Iddo Tzameret

19

Setidaknya ada dua baris penelitian tentang acak untuk rumus dengan klausa / variabel-rasio lebih besar dari ambang kepuasan: $k\text-\mathsf{SAT}$

Untuk formula demikian batas bawah pada panjang penolakan dalam resolusi dan sistem bukti proposisional yang lebih kuat telah ditunjukkan, dimulai dengan makalah " Banyak contoh sulit untuk resolusi " oleh Chvátal dan Szemerédi. Resolusi batas bawah ini menyiratkan batas bawah pada runtime pemecah SAT-DPLL dan CDCL. Batas bawah terkuat adalah untuk Kalkulus Polinomial, karena Ben-Sasson dan Impagliazzo .
Untuk rumus seperti itu ada algoritma deterministik yang efisien untuk mensertifikasi ketidakpuasan, yaitu algoritma yang menghasilkan "UNSAT" atau "Tidak Tahu", di mana jawaban "UNSAT" harus benar, dan harus menampilkan "UNSAT" pada formula tidak memuaskan dengan probabilitas tinggi. Hasil terkuat ke arah itu adalah karena Feige dan Ofek .

Jan Johannsen
sumber

Mungkin perlu dicatat bahwa Chvátal / Szemerédi menunjukkan bahwa whp rumus -SAT acak dengan tidak memuaskan. Feige dan Ofek memberikan algoritma spektral ketika . Jadi masih ada celah antara dan mana hampir setiap formula tidak memuaskan, tetapi kami tidak tahu bagaimana memutuskan bahwa ini benar.

k

$k$

m / n \geq c_{1}

$m/n \ge c_1$

m / n \geq c_{2} n^{1 / 2}

$m/n \ge c_2n^{1/2}$

\sqrt{n}

$\sqrt{n}$

c_{1} n

$c_1n$

c_{2} n^{3 / 2}

$c_2n^{3/2}$

András Salamon

2

di sini adalah studi / sudut pandang yang lebih tua namun relevan oleh seorang ahli terkemuka.

Tepian pisau kendala Walsh 1998

ia menunjukkan parameter memperkirakan sejumlah solusi dan ukuran "kendala" dan berkorelasi / tren secara kasar dengan rasio klausa terhadap variabel. lihat p3 gambar 4 khususnya $\kappa$

Pada Gambar 4, kami memplot kendala yang diperkirakan turun ke cabang heuristik untuk masalah 3-SAT acak. Untuk L / N <4.3, masalah di bawah dibatasi dan larut. Saat penelusuran berlanjut, berkurang karena masalah menjadi lebih terbatas dan jelas larut. Untuk L / N> 4.3, masalah terlalu dibatasi dan tidak dapat larut. Saat penelusuran berlanjut, meningkat karena masalah menjadi lebih dibatasi dan jelas tidak dapat larut. $\kappa$ $\kappa$

pertanyaannya tentang . tetapi ini dikenal dari analisis empiris yang sangat dibatasi dan oleh karena itu pada dasarnya mendekati contoh waktu-P (seorang pemecah "cepat" menemukan mereka tidak dapat diselesaikan) dan oleh karena itu tidak secara teoritis menarik (karena mereka tidak "memperoleh / melaksanakan" waktu eksponensial-waktu) -perilaku pemecah rata-rata). Namun, belum secara pribadi melihat makalah / transformasi / teori yang membuktikan ini lebih secara teoritis / ketat (selain makalah ini sebagai awal dari itu). $m/n \gg\alpha$

ay
sumber

di sisi lain mungkin untuk menghasilkan instance "keras" individual dari setiap m / n "dimensi", hanya saja mereka secara statistik lebih kecil kemungkinannya di luar transisi fase "P-NP-P".

vzn

Apakah ada penelitian tentang -SAT di atas ambang batas kepuasan?

Jawaban: