<p>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.</p>

<ul>
<li><a href="http://users.soe.ucsc.edu/~kolaitis/theses/bailey-dissertation.pdf" rel="nofollow">PHASE TRANSITIONS OF BOOLEAN SATISFIABILITY VARIANTS</a>, Bailey 2004</li>
</ul>

CC BY-SA 3.0
2014-02-18T03:46:12.120Z
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](http://www.cs.cornell.edu/selman/papers/pdf/96.aij.critical_behavior_cost.pdf) 1996 Selman/Kirkpatrick see eg p276. [wish there were newer refs/study on this subj, havent seen them]
vzn
CC BY-SA 3.0
2014-02-13T22:12:21.340Z
2014-02-13T22:12:21.340Z
vzn
<p>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?</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2014-02-11T19:04:22.737Z
I don't think there is a formula. See Moshe Vardi's [talk](http://videos.birs.ca/2014/14w5101/201401231116-Vardi.mp4) about phase transition.
Kaveh
CC BY-SA 3.0
2014-02-11T20:21:00.380Z
Tyr to use surround your latex code with $ to make it more readable.
I am unsure how you wanted it to display
Martin Vatshelle
CC BY-SA 3.0
2014-02-11T20:39:59.177Z
what is an "empirical formula"?
Sasho Nikolov
CC BY-SA 3.0
2014-02-11T22:05:12.267Z
@Kaveh - thanks for the video. Very enlightening.
dcs
CC BY-SA 3.0
2014-02-11T22:06:50.853Z
@Sasho - Hoping to find an empirically good formula based on statistical observations (rather than necessarily having been rigorously proven)
dcs
CC BY-SA 3.0
2014-02-12T11:30:31.297Z
See the answers at https://cstheory.stackexchange.com/q/14953/109 for several key references.  This actually seems borderline a duplicate of that question?
András Salamon
<random-k-sat>
Empirical probability of k-SAT satisfiability
dcs
# Empirical probability of k-SAT satisfiability

(Asked by: username_0 on 2014-02-11)

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?

**Tags:** random-k-sat
> **Comments:**
> **username_1**: I don't think there is a formula. See Moshe Vardi's [talk](http://videos.birs.ca/2014/14w5101/201401231116-Vardi.mp4) about phase transition.  
> **username_2**: Tyr to use surround your latex code with $ to make it more readable. I am unsure how you wanted it to display  
> **username_3**: what is an "empirical formula"?  
> **username_0**: @Kaveh - thanks for the video. Very enlightening.  
> **username_0**: @Sasho - Hoping to find an empirically good formula based on statistical observations (rather than necessarily having been rigorously proven)  
> **username_4**: See the answers at https://cstheory.stackexchange.com/q/14953/109 for several key references.  This actually seems borderline a duplicate of that question?  

---

## 1 answers

### Answer by username_5 on 2014-02-13. Score: 4 | Accepted answer

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.

* [PHASE TRANSITIONS OF BOOLEAN SATISFIABILITY VARIANTS](http://users.soe.ucsc.edu/~kolaitis/theses/bailey-dissertation.pdf), Bailey 2004

> **Comments:**
> **username_5**: 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](http://www.cs.cornell.edu/selman/papers/pdf/96.aij.critical_behavior_cost.pdf) 1996 Selman/Kirkpatrick see eg p276. [wish there were newer refs/study on this subj, havent seen them]  

---

