Apa batas atas dan bawah yang paling dikenal saat ini pada ambang pemenuhan (un) untuk k-sat acak dan / atau 3-sat?

Saya ingin mengetahui keadaan transisi fase saat ini untuk k-sat acak, mengingat n variabel dan klausa m, apa yang paling dikenal c = m / n untuk batas atas dan bawah.

Dimitris Achlioptas membahas hal ini dalam artikel surveynya dari Handbook of Satisfiability ( PDF ).

Ada dugaan untuk menjadi ambang tunggal untuk setiap , sehingga ketika maka rumus acak -SAT dengan klausa dan variabel tidak memuaskan dengan probabilitas tinggi, dan ketika maka clause acak , -variabel -SAT memuaskan dengan probabilitas tinggi. (Lebih tepatnya, dugaan adalah bahwa dalam batas cenderung tak terhingga, probabilitas kepuasan adalah 0 atau 1 dalam dua rezim ini, masing-masing.) k ≥ 3 m / n > r k k m n m / n < r k m n k $r_k$$k \ge 3$$m/n > r_k$$k$$m$$n$$m/n < r_k$$m$$n$$k$$n$

Dengan asumsi bahwa dugaan Ambang Batas Kepuasan ini berlaku, batas yang paling dikenal untuk adalah$r_k$

k 3 4 5 7 10 20
Batas atas terbaik 4,51 10,23 21,33 87,88 708,94 726,817
Batas bawah terbaik 3.52 7.91 18.79 84.82 704.94 726.809

(tabel ini muncul di halaman yang ditunjukkan sebagai 247 dalam konsep).

Dalam naskah yang lebih baru (arXiv: 1411.0650 ), Jian Ding, Allan Sly dan Nike Sun menunjukkan bahwa untuk semua cukup besar , sebenarnya ada ambang tunggal , dan istilah kesalahan dalam ekspresi ini menjadi nol karena cenderung tak terhingga.r k = 2 k ln 2 - ( 1 + ln 2 ) / 2 + o ( 1 ) o ( 1 ) $k$$r_k = 2^k\ln 2 - (1+\ln 2)/2 + o(1)$$o(1)$$k$