Batas ketat saat ini untuk kerapatan 3-SAT kritis

Saya tertarik pada kerapatan α 3-satisfiability (3-SAT) yang kritis . Diduga bahwa α seperti itu ada: jika jumlah klausa 3-SAT yang dihasilkan secara acak adalah ( α + ϵ ) n atau lebih, mereka hampir pasti tidak memuaskan. (Di sini ϵ adalah konstanta kecil dan n adalah jumlah variabel.) Jika angkanya ( α - ϵ ) n atau kurang, mereka hampir pasti memuaskan.$\alpha$$\alpha$$(\alpha + \epsilon) n$$\epsilon$$n$$(\alpha - \epsilon) n$

Algoritma propagasi Belief tesis untuk masalah kepuasan kendala oleh Elitza Nikolaeva Maneva menantang masalah dari sudut propagasi kepercayaan yang dikenal dalam teori informasi. Pada halaman 13, dikatakan jika α ada.$3.52<\alpha<4.51$$\alpha$

Apa batas yang paling dikenal untuk ?$\alpha$

Terlepas dari teorema Friedgut tentang -SAT, sementara kami kekurangan teknik untuk dapat diabaikan ϵ untuk k kecil , tampaknya lebih berguna untuk berbicara tentang ambang tingkat kepuasan ( α - ϵ ) dan ambang ketidakpuasan ( α + ϵ ) sebagai entitas yang terpisah.$k$$\epsilon$$k$$\alpha - \epsilon$$\alpha + \epsilon$

Ambang ketidakpuasan diketahui paling banyak 4,4898, sedikit perbaikan sejak tesis Maneva 2001.

• J. Díaz, L. Kirousis, D. Mitsche, X. Pérez-Gimenéz. Pada ambang pemenuhan formula dengan tiga liter per klausa , Theoretical Computer Science 410 , 2009, 2920–2934. doi: 10.1016 / j.tcs.2009.02.020 ( pracetak dari salah satu penulis )

Ambang batas kepuasan diketahui setidaknya 3,52, yang tidak berubah dari saat tesis Maneva.

• AC Kaporis, LM Kirousis, EG Lalas. Analisis Probabilistik dari Algoritma Kepuasan Serakah , Struktur dan Algoritma 28 , 2006, 444-480 acak. doi: 10.1002 / rsa.20104

Batas-batas ini baru-baru ini dikutip oleh Achlioptas dan Menchaca-Mendez sebagai yang paling dikenal hingga saat ini.

• D. Achlioptas, R. Menchaca-Mendez. Batas Ketidakpuasan untuk CSP Acak dari Metode Interpolasi Energetik , ICALP 2012, LNCS 7391, 1–12. doi: 10.1007 / 978-3-642-31594-7_1

Ada kertas 58 halaman baru (32 referensi) diterima untuk STOC 2013,

Pergi setelah ambang k-SAT oleh Coja-Oghlan dan Konstantinos Panagiotou

yang mensurvei dan memajukan bidang penentuan ambang k-SAT yang tepat, membangun terutama dari hasil yang dipinjam dari fisika statistik. Dari abstrak:

$\ln 2 − {1 \over 2} +O(1/k) \approx 0.19$

$k$