# Random 3-SAT: What is the consensus experimental range of the threshold?

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.

• You need to define what it means for a ratio to be critcal. Dec 4, 2013 at 22:33
• 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$ Dec 5, 2013 at 3:30
• Dec 5, 2013 at 16:11
• 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.) Jan 8, 2014 at 22:11