<p>Dimitris Achlioptas covers this in a survey article from the first edition of the Handbook of Satisfiability (<a href="https://di.uoa.gr/%7Eoptas/papers/handbook.pdf" rel="nofollow noreferrer">PDF of draft</a>).</p>
<p>There is conjectured to be a single threshold <span class="math-container">$r_k$</span> for each <span class="math-container">$k \ge 3$</span>, so that when <span class="math-container">$m/n &gt; r_k$</span> then a random <span class="math-container">$k$</span>-SAT formula with <span class="math-container">$m$</span> clauses and <span class="math-container">$n$</span> variables is unsatisfiable with high probability, and so that when <span class="math-container">$m/n &lt; r_k$</span> then a random <span class="math-container">$m$</span>-clause, <span class="math-container">$n$</span>-variable <span class="math-container">$k$</span>-SAT formula is satisfiable with high probability.
(More precisely, the conjecture is that in the limit as <span class="math-container">$n$</span> tends to infinity, the probability of satisfiability is 0 or 1 in these two regimes, respectively.)</p>
<p>Assuming that this Satisfiability Threshold Conjecture holds, the best known bounds for <span class="math-container">$r_k$</span> are</p>
<pre>
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
</pre>
<p>(this table appears on the page indicated as 247 in the draft).</p>
<p>In a more recent manuscript (arXiv:<a href="https://arxiv.org/abs/1411.0650" rel="nofollow noreferrer">1411.0650</a>), Jian Ding, Allan Sly and Nike Sun showed that for all sufficiently large <span class="math-container">$k$</span>, there is in fact a single threshold <span class="math-container">$r_k = 2^k\ln 2 - (1+\ln 2)/2 + o(1)$</span>, and the error term <span class="math-container">$o(1)$</span> in this expression goes to zero as <span class="math-container">$k$</span> tends to infinity.</p>

CC BY-SA 4.0
2021-10-20T10:39:05.227Z
Unfortunately in the 2nd edition of the Handbook this table is unpopulated (it contains some placeholders but no actual values).
András Salamon
CC BY-SA 4.0
2023-07-08T20:08:36.737Z
I suppose this is for when all clauses have width exactly $k$.
rus9384
CC BY-SA 4.0
2010-10-22T17:59:58.887Z
2021-10-20T10:58:45.527Z
2021-10-20T10:58:45.527Z
András Salamon
<p>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.</p>

CC BY-SA 3.0
2011-08-03T02:18:02.707Z
@Tayfun Pay: I am commenting here because you have deleted your questions and I can't comment there. Sorry, I didn't meant to be rude, I was asking for motivation to understand why you are interested in the question. In the other case, if you write down the definitions you will see the difference between them (many-one reductions does not need to preserve the number of certificates, it can map an instance of the problem A to an instance of problem B and there is no condition on the certificates at all). I think it would be better if you migrated the question to Math.SE. (more)
Kaveh
CC BY-SA 3.0
2011-08-03T02:21:20.273Z
There is nothing wrong with moving a question to Math.SE, I myself sometimes ask questions that are not research level over there. Let me know if you decide to improve the deleted question or migrate the second one to Math.SE and I can undelete them for you (and give a more detailed answer for the second one over there).
Kaveh
CC BY-SA 3.0
2015-02-13T09:53:42.413Z
See also subsequent question https://cstheory.stackexchange.com/questions/22016/has-there-been-any-research-on-k-sat-above-the-satisfiability-threshold for additional pointers to work exploring the phase transition.
András Salamon
CC BY-SA 4.0
2021-11-09T14:36:29.463Z
see old franco survey.  very different transition behavior on regular graph coloring cnfs. +daniel GREs2380
daniel pehoushek
CC BY-SA 2.5
2010-09-30T15:15:41.493Z
Did you try a reference search?  cf. http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question
RJK
CC BY-SA 2.5
2010-09-30T15:23:45.273Z
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.)
RJK
CC BY-SA 2.5
2010-09-30T15:39:42.207Z
See http://cstheory.stackexchange.com/questions/1130/what-does-one-mean-by-heuristic-statistical-physics-arguments/1229#1229 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.
András Salamon
CC BY-SA 2.5
2010-10-25T12:45:35.023Z
You may find this question useful: http://cstheory.stackexchange.com/questions/2168/how-many-instances-of-3-sat-are-satisfiable/2171#2171. In particular, see the first answer.
Giorgio Camerani
<cc.complexity-theory><sat><lower-bounds><upper-bounds><phase-transition>
What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?
Tayfun Pay
# What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?

(Asked by: username_0 on 2010-09-30)

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.

**Tags:** cc.complexity-theory, sat, lower-bounds, upper-bounds, phase-transition

> **Comments:**
> **username_4**: Did you try a reference search?  cf. http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question  
> **username_4**: 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.)  
> **username_2**: See http://cstheory.stackexchange.com/questions/1130/what-does-one-mean-by-heuristic-statistical-physics-arguments/1229#1229 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.  
> **username_5**: You may find this question useful: http://cstheory.stackexchange.com/questions/2168/how-many-instances-of-3-sat-are-satisfiable/2171#2171. In particular, see the first answer.  
> **username_1**: @username_0: I am commenting here because you have deleted your questions and I can't comment there. Sorry, I didn't meant to be rude, I was asking for motivation to understand why you are interested in the question. In the other case, if you write down the definitions you will see the difference between them (many-one reductions does not need to preserve the number of certificates, it can map an instance of the problem A to an instance of problem B and there is no condition on the certificates at all). I think it would be better if you migrated the question to Math.SE. (more)  
> **username_1**: There is nothing wrong with moving a question to Math.SE, I myself sometimes ask questions that are not research level over there. Let me know if you decide to improve the deleted question or migrate the second one to Math.SE and I can undelete them for you (and give a more detailed answer for the second one over there).  
> **username_2**: See also subsequent question https://cstheory.stackexchange.com/questions/22016/has-there-been-any-research-on-k-sat-above-the-satisfiability-threshold for additional pointers to work exploring the phase transition.  
> **username_3**: see old franco survey.  very different transition behavior on regular graph coloring cnfs. +daniel GREs2380  

---

## 1 answers

### Answer by username_2 on 2010-10-22. Score: 20 | Accepted answer

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.

> **Comments:**
> **username_2**: Unfortunately in the 2nd edition of the Handbook this table is unpopulated (it contains some placeholders but no actual values).  
> **username_6**: I suppose this is for when all clauses have width exactly $k$.  

---

