# Empirical probability of k-SAT satisfiability

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?

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