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...
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...
Apakah ada pekerjaan yang telah dilakukan tentang bagaimana kompleksitas kejadian acak # 2-SAT bervariasi dengan kepadatan klausa? Yaitu: bagaimana kesulitan menghitung solusi yang memuaskan untuk contoh 2-SAT yang dihasilkan secara acak bervariasi, karena kepadatan klausa bervariasi? Secara...
Sudah diketahui bahwa rumus acak -CNF atas variabel dengan klausa tidak memuaskan (yaitu mereka kontradiksi) dengan probabilitas tinggi, untuk konstanta yang cukup besar . Dengan demikian, rumus acak -CNF (untuk cukup besar) merupakan distribusi alami atas formula Boolean yang tidak memuaskan (atau...
Rasio kritis klausa terhadap variabel untuk acak 3-SAT adalah lebih dari 3 dan kurang dari 6, dan tampaknya secara umum digambarkan sebagai "sekitar 4,2" atau "sekitar 4,25". Mezard, Parisi, dan Zecchina membuktikan (dalam pengertian fisika) bahwa rasio kritis adalah 4,256, sedangkan penulis...
Makalah baru-baru ini dari FOCS2013, Strong Backdoors ke Bounded Treewidth SAT oleh Gaspers dan Szeider berbicara tentang hubungan antara treewidth grafik klausa SAT dan kekerasan contoh. Untuk 3-SAT acak, yaitu instance 3-SAT yang dipilih secara acak, apa korelasi antara treewidth grafik klausa...