16
$\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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You need to define what it means for a ratio to be critcal. $\endgroup$
    – Tyson Williams
    Commented 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$
    – Sasho Nikolov
    Commented Dec 5, 2013 at 3:30
  • $\begingroup$ possible duplicate of What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat? $\endgroup$
    – András Salamon
    Commented Dec 5, 2013 at 16:11
  • $\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
    Commented Jan 8, 2014 at 22:11

2 Answers 2

Reset to default
10
$\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.

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

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.

Improve this answer
$\endgroup$

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.