The critical ratio of clauses to variables for random 3-SAT is more than 3 and less than 6, and seems to be commonly described as "around 4.2" or "around 4.25". Mezard, Parisi, and Zecchina prove (in the physics sense) that the critical ratio is 4.256, whereas the first and third authors prove that it is 4.267.

What is the range of values that the critical ratio could possibly take?

The motivation for me asking this question is that if the ratio could be $2+\sqrt{5} \approx 4.236$, then the standard reduction of 3-SAT to NAE-3-SAT (transforming $m$ clauses and $n$ variables into $2m$ clauses and $m+n+1$ variables) gives a ratio of $\phi$, which seems unlikely but would be pretty cool.

  • 1
    $\begingroup$ You need to define what it means for a ratio to be critcal. $\endgroup$ Dec 4, 2013 at 22:33
  • 5
    $\begingroup$ I think this is standard terminology: the critical ratio is the real number $\alpha$ such that random 3-SAT formulas with $< \alpha n$ clauses are almost surely satisfiable, and random 3-SAT formulas with $> \alpha n$ clauses are almost surely not satisfiable. almost surely here means the probability goes to $1$ as $n \to \infty$ $\endgroup$ Dec 5, 2013 at 3:30
  • $\begingroup$ I contend that the question is distinct. I'm looking for some estimate of the set of values that, say, would not shock any expert in the community. I don't think anything below 4, for example, qualifies. (I realize that this is, to an extent, subject to individual mileage.) $\endgroup$ Jan 8, 2014 at 22:11

2 Answers 2


In light of the Ding--Sly--Sun verification of the 1-step Replica Symmetry Breaking picture for kSAT (when k is large enough) I think experts would now be pretty surprised if the MPZ/MMZ-conjectured formula for the 3SAT satisfiability threshold (approximate value: 4.2667) is incorrect.

  • 2
    $\begingroup$ I think this is the paper mentioned in this answer, by Jian Ding, Allan Sly, and Nike Sun (118 pages!). $\endgroup$
    – Moot
    Jun 11, 2017 at 2:49

From the engeneering point of view, when not allowing any irrationalities like the golden ratio, the practical thershold should be 4,109890672858455 the exact one as long you don't consider any theoretical 1 million variables formulas or such.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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