Given a random instance $I_m = I_m(n,k)$ of $k$-SAT with $n$ variables and $m$ clauses, what's the probability $I_m$ is satisfiable?

It's believed that there's a threshold above which satisfiability becomes less likely as $m/n$ increases. The reverse is true as $m/n$ decreases.

Is there an empirical formula for $3$-SAT and other $k$'s that describe the rate at which satisfiability becomes more/less likely as you move away from the threshold?

  • 1
    $\begingroup$ I don't think there is a formula. See Moshe Vardi's talk about phase transition. $\endgroup$
    – Kaveh
    Feb 11 '14 at 19:04
  • $\begingroup$ Tyr to use surround your latex code with $ to make it more readable. I am unsure how you wanted it to display $\endgroup$ Feb 11 '14 at 20:21
  • 1
    $\begingroup$ what is an "empirical formula"? $\endgroup$ Feb 11 '14 at 20:39
  • $\begingroup$ @Kaveh - thanks for the video. Very enlightening. $\endgroup$
    – dcs
    Feb 11 '14 at 22:05
  • 1
    $\begingroup$ See the answers at cstheory.stackexchange.com/q/14953/109 for several key references. This actually seems borderline a duplicate of that question? $\endgroup$ Feb 12 '14 at 11:30

see eg sec 4.7.4 p103 of this thesis where a finite-size scaling formula based on a power law is applied and coefficients fit with experimental data.

  • $\begingroup$ fyi/addendum nobody called this out but full disclosure, that section seems to be on bounded SAT which is closely related to k-SAT but not the same. however the empirical formulas seem to be almost the same for k-SAT & they seem to have originated in statistical physics spin-glass transition point formulas. another ref critical behavior in the computational cost of satisfiability checking 1996 Selman/Kirkpatrick see eg p276. [wish there were newer refs/study on this subj, havent seen them] $\endgroup$
    – vzn
    Feb 18 '14 at 3:46

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.