Каковы текущие наиболее известные верхние и нижние границы порога (не) выполнимости для случайных k-sat и / или 3-sat?

Я хотел бы знать текущее состояние фазового перехода для случайных k-sat, учитывая n переменных и m предложений, что является наиболее известным c = m / n для верхней и нижней границ.

Димитрис Ахлиоптас рассказывает об этом в своей обзорной статье из «Руководства по удовлетворенности» ( PDF ).

$r_k$$k \ge 3$$m/n > r_k$$k$$m$$n$$m/n < r_k$$m$$n$$k$$n$ стремится к бесконечности, вероятность выполнимости равна 0 или 1 в этих двух режимах, соответственно.)

$r_k$

k 3 4 5 7 10 20
Лучшая верхняя граница 4,51 10,23 21,33 87,88 708,94 726 817
Лучшая нижняя граница 3,52 7,91 18,79 84,82 704,94 726 809

(эта таблица появляется на странице, обозначенной как 247 в черновике).

$k$$r_k = 2^k\ln 2 - (1+\ln 2)/2 + o(1)$$o(1)$$k$