I would like to know the current state of the phase transition for random k-sat, given n variables and m clauses, what is the best known c=m/n for upper and lower bounds.

  • 2
    $\begingroup$ Did you try a reference search? cf. meta.cstheory.stackexchange.com/questions/300/… $\endgroup$
    – RJK
    Sep 30, 2010 at 15:15
  • 3
    $\begingroup$ PS It looks to me like the second hit on Google is a freely-accessible article with answers to your question. (A 2009 arXiv article by Coja-Oghlan.) $\endgroup$
    – RJK
    Sep 30, 2010 at 15:23
  • $\begingroup$ See cstheory.stackexchange.com/questions/1130/… for a reasonably up to date perspective. Follow-ups by the people working in this area, such as Amin Coja-Oghlan and Dimitris Achlioptas, then have the answer you are looking for. $\endgroup$ Sep 30, 2010 at 15:39
  • $\begingroup$ I still have not gotten a definite answer. I'll appreciate it if someone can give me a definite answer. Thanks $\endgroup$
    – Tayfun Pay
    Oct 5, 2010 at 22:13
  • $\begingroup$ You may find this question useful: cstheory.stackexchange.com/questions/2168/…. In particular, see the first answer. $\endgroup$ Oct 25, 2010 at 12:45

1 Answer 1


Dimitris Achlioptas covers this in a survey article from the first edition of the Handbook of Satisfiability (PDF of draft).

There is conjectured to be a single threshold $r_k$ for each $k \ge 3$, so that when $m/n > r_k$ then a random $k$-SAT formula with $m$ clauses and $n$ variables is unsatisfiable with high probability, and so that when $m/n < r_k$ then a random $m$-clause, $n$-variable $k$-SAT formula is satisfiable with high probability. (More precisely, the conjecture is that in the limit as $n$ tends to infinity, the probability of satisfiability is 0 or 1 in these two regimes, respectively.)

Assuming that this Satisfiability Threshold Conjecture holds, the best known bounds for $r_k$ are

k                   3      4      5     7     10      20
Best upper bound 4.51  10.23  21.33 87.88 708.94 726,817
Best lower bound 3.52   7.91  18.79 84.82 704.94 726,809

(this table appears on the page indicated as 247 in the draft).

In a more recent manuscript (arXiv:1411.0650), Jian Ding, Allan Sly and Nike Sun showed that for all sufficiently large $k$, there is in fact a single threshold $r_k = 2^k\ln 2 - (1+\ln 2)/2 + o(1)$, and the error term $o(1)$ in this expression goes to zero as $k$ tends to infinity.

  • $\begingroup$ Unfortunately in the 2nd edition of the Handbook this table is unpopulated (it contains some placeholders but no actual values). $\endgroup$ Oct 20, 2021 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.