<p>Notwithstanding Friedgut's theorem about $k$-SAT, while we lack techniques to get to negligible $\epsilon$ for small $k$, it seems more useful to talk about the satisfiability threshold ($\alpha - \epsilon$) and the unsatisfiability threshold ($\alpha + \epsilon$) as separate entities.</p>

<p>The unsatisfiability threshold is known to be at most 4.4898, a slight improvement since Maneva's 2001 thesis.</p>

<ul>
<li>J. Díaz, L. Kirousis, D. Mitsche, X. Pérez-Gimenéz.  <em>On the satisfiability threshold of formulas with three literals per clause</em>, Theoretical Computer Science <strong>410</strong>, 2009, 2920–2934. <a href="http://dx.doi.org/10.1016/j.tcs.2009.02.020">doi:10.1016/j.tcs.2009.02.020</a> (<a href="http://math.ryerson.ca/~dmitsche/DKMP09.pdf">preprint from one of the authors</a>)</li>
</ul>

<p>The satisfiability threshold is known to be at least 3.52, which is unchanged from the time of Maneva's thesis.</p>

<ul>
<li>A. C. Kaporis, L. M. Kirousis, E. G. Lalas.  <em>The Probabilistic Analysis of a Greedy Satisfiability Algorithm</em>, Random Structures and Algorithms <strong>28</strong>, 2006, 444–480.  <a href="http://dx.doi.org/10.1002/rsa.20104">doi:10.1002/rsa.20104</a></li>
</ul>

<p>These bounds were recently cited by Achlioptas and Menchaca-Mendez as the best known to date.</p>

<ul>
<li>D. Achlioptas, R. Menchaca-Mendez.  <em>Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method</em>, ICALP 2012, LNCS 7391, 1–12.  <a href="http://dx.doi.org/10.1007/978-3-642-31594-7_1">doi:10.1007/978-3-642-31594-7_1</a></li>
</ul>

CC BY-SA 3.0
2013-01-06T15:33:12.610Z
2013-01-06T16:40:37.717Z
2013-01-06T16:40:37.717Z
András Salamon
<p>There is a new 58 page paper (32 refs) accepted to STOC 2013,</p>

<blockquote>
  <p><a href="http://arxiv.org/pdf/1212.1682v1.pdf" rel="nofollow noreferrer">Going after the k-SAT threshold</a> by Coja-Oghlan and Konstantinos Panagiotou</p>
</blockquote>

<p>that surveys and advances the area of determining the precise k-SAT threshhold, building especially from results borrowed from statistical physics. From the abstract:</p>

<blockquote>
  <p>Here we develop a new asymmetric second
  moment method that allows us to tackle this issue head on for the first time in the theory of random CSPs. This
  technique enables us to compute the k-SAT threshold up to an additive <span class="math-container">$\ln 2 − {1 \over 2}
 +O(1/k) \approx 0.19$</span>.</p>
</blockquote>

<p><em>Coja-Oghlan, Amin; Panagiotou, Konstantinos</em>, <a href="http://dx.doi.org/10.1145/2488608.2488698" rel="nofollow noreferrer"><strong>Going after the <span class="math-container">$k$</span>-SAT threshold</strong></a>, Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 705-714 (2013). <a href="https://zbmath.org/?q=an:1293.68164" rel="nofollow noreferrer">ZBL1293.68164</a>.</p>

CC BY-SA 4.0
2013-02-11T23:51:11.523Z
2019-03-26T21:09:04.540Z
2019-03-26T21:09:04.540Z
vzn
<p>I'm interested in the critical <a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability">3-satisfiability</a> (3-SAT) density $\alpha$. It's conjectured that such $\alpha$ exists: if the number of randomly generated 3-SAT clauses is $(\alpha + \epsilon) n$ or more, they are almost surely unsatisfiable.
(Here $\epsilon$ is any small constant and $n$ is the number of variables.)
If the number is $(\alpha - \epsilon) n$ or less, they are almost surely satisfiable.</p>

<p>The thesis <em><a href="http://www.maia.ub.edu/~maneva/papers/thesis.pdf">Belief propagation algorithms for constraint satisfaction problems </a></em> by Elitza Nikolaeva Maneva challenges the problem from the angle of belief propagation known in information theory. On page 13, it says $3.52&lt;\alpha&lt;4.51$ if $\alpha$ exists. </p>

<p>What are the best known bounds for $\alpha$?</p>

CC BY-SA 3.0
2013-01-12T10:07:25.197Z
See also question http://cstheory.stackexchange.com/q/1130
András Salamon
<pr.probability><random-k-sat>
Current tightest bounds for critical 3-SAT density
Jun
# Current tightest bounds for critical 3-SAT density

(Asked by: username_0 on 2013-01-03)

I'm interested in the critical [3-satisfiability](http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability) (3-SAT) density $\alpha$. It's conjectured that such $\alpha$ exists: if the number of randomly generated 3-SAT clauses is $(\alpha + \epsilon) n$ or more, they are almost surely unsatisfiable.
(Here $\epsilon$ is any small constant and $n$ is the number of variables.)
If the number is $(\alpha - \epsilon) n$ or less, they are almost surely satisfiable.

The thesis *[Belief propagation algorithms for constraint satisfaction problems](http://www.maia.ub.edu/~maneva/papers/thesis.pdf)*  by Elitza Nikolaeva Maneva challenges the problem from the angle of belief propagation known in information theory. On page 13, it says $3.52<\alpha<4.51$ if $\alpha$ exists.

What are the best known bounds for $\alpha$?

**Tags:** pr.probability, random-k-sat

> **Comments:**
> **username_1**: See also question http://cstheory.stackexchange.com/q/1130  

---

## 2 answers

### Answer by username_1 on 2013-01-06. Score: 17

Notwithstanding Friedgut's theorem about $k$-SAT, while we lack techniques to get to negligible $\epsilon$ for small $k$, it seems more useful to talk about the satisfiability threshold ($\alpha - \epsilon$) and the unsatisfiability threshold ($\alpha + \epsilon$) as separate entities.

The unsatisfiability threshold is known to be at most 4.4898, a slight improvement since Maneva's 2001 thesis.

* J. Díaz, L. Kirousis, D. Mitsche, X. Pérez-Gimenéz. *On the satisfiability threshold of formulas with three literals per clause*, Theoretical Computer Science **410**, 2009, 2920–2934. [doi:10.1016/j.tcs.2009.02.020](http://dx.doi.org/10.1016/j.tcs.2009.02.020) ([preprint from one of the authors](http://math.ryerson.ca/~dmitsche/DKMP09.pdf))

The satisfiability threshold is known to be at least 3.52, which is unchanged from the time of Maneva's thesis.

* A. C. Kaporis, L. M. Kirousis, E. G. Lalas. *The Probabilistic Analysis of a Greedy Satisfiability Algorithm*, Random Structures and Algorithms **28**, 2006, 444–480. [doi:10.1002/rsa.20104](http://dx.doi.org/10.1002/rsa.20104)

These bounds were recently cited by Achlioptas and Menchaca-Mendez as the best known to date.

* D. Achlioptas, R. Menchaca-Mendez. *Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method*, ICALP 2012, LNCS 7391, 1–12. [doi:10.1007/978-3-642-31594-7\_1](http://dx.doi.org/10.1007/978-3-642-31594-7_1)


---

### Answer by username_2 on 2013-02-11. Score: 6

There is a new 58 page paper (32 refs) accepted to STOC 2013,

> [Going after the k-SAT threshold](http://arxiv.org/pdf/1212.1682v1.pdf) by Coja-Oghlan and Konstantinos Panagiotou

that surveys and advances the area of determining the precise k-SAT threshhold, building especially from results borrowed from statistical physics. From the abstract:

> Here we develop a new asymmetric second
> moment method that allows us to tackle this issue head on for the first time in the theory of random CSPs. This
> technique enables us to compute the k-SAT threshold up to an additive $\ln 2 − {1 \over 2}
> +O(1/k) \approx 0.19$.

*Coja-Oghlan, Amin; Panagiotou, Konstantinos*, [**Going after the $k$-SAT threshold**](http://dx.doi.org/10.1145/2488608.2488698), Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, username_0e 1--4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 705-714 (2013). [ZBL1293.68164](https://zbmath.org/?q=an:1293.68164).


---

