Apa kompleksitas penghitungan 2-SAT acak?

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 khusus, apakah ada hasil yang diketahui melibatkan melibatkan ambang kritis?

Tentu saja, karena 2-SAT  ∈  P , kompleksitas penghitungan tipikal sebagian tergantung pada probabilitas dengan mana sebuah instance memuaskan; contoh yang kepadatan klausa di atas ambang kritis untuk SAT / UNSAT biasanya akan memiliki kompleksitas penghitungan yang mudah, karena jawabannya adalah " nol " hampir pasti, dalam batas n  . Namun, kompleksitas penghitungan mungkin masih mudah untuk instance 2-SAT yang memiliki kepadatan mendekati atau tepat di atas ambang kritis untuk hingga n : orang mungkin berharap bahwa instance yang memuaskan hanya akan memiliki sejumlah kecil solusi, yang mungkin mudah untuk menghitung karena ketatnya kendala.$\to \infty$

Untuk k -SAT dengan k  ≥ 3, kesulitan menentukan apakah sebuah instance memenuhi atau tidak memuaskan tampaknya lebih tinggi di dekat ambang kritis yang memisahkan fase SAT dari fase UNSAT, sebagian ketika seseorang mencoba untuk menentukan apakah ada setidaknya satu instance solusi yang memuaskan. Untuk # 2-SAT , kesulitannya tidak terletak pada menentukan apakah setidaknya ada satu solusi; jadi orang harus berharap bahwa kesulitannya mungkin dalam menentukan jumlah solusi untuk formula yang memuaskan dari yang signifikan tetapi tidak besar sejumlah kendala - yaitu, di mana ada cukup kendala untuk menginduksi dependensi non-sepele antara variabel, tetapi tidak terlalu banyak untuk terlalu menentukan tugas yang mungkin.

Mungkin tulisan ini dapat membantu Anda:

Batas Atas Kasus Terburuk Baru untuk # 2-SAT dan # 3-SAT dengan Jumlah Klausa sebagai Parameter oleh J. Zhou, M. Yin, C. Zhou (2010).

Dan ini yang mempelajari struktur dari set solusi dari contoh 2-SAT acak: Penugasan yang Memuaskan dari Masalah Kepuasan Kendala Kendala Acak Boolean: Clusters and Overlaps oleh G. Istrate (2007)