14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You need to define what it means for a ratio to be critcal. $\endgroup$ – Tyson Williams Dec 4 '13 at 22:33
  • 3
    $\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$ – Sasho Nikolov Dec 5 '13 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$ – Andrew D. King Jan 8 '14 at 22:11
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\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 '17 at 2:49

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.