3
$\begingroup$

This is not a technical question, I hope this community has a room for such questions, but I will delete it in case this is inappropriate.

It has been experimentally observed (e.g. here) that when choosing a $3$-SAT formula by the following process:

On input $(n, \alpha n)$: choose $\alpha n$ clauses uniformly at random from the set of all clauses of $3$ literals over $x_1, \ldots, x_n$, and return the conjunction of these clauses.

The probability that the outputted formula is satisfiable depends on $\alpha$: if $\alpha \ll c$ the probability is very close to $1$, and if $\alpha \gg c$ the probability is very close to $0$ (it has been observed for a general $k$-SAT instances).

My question is what is the theoretical understanding of this problem? To the best of my knowledge, for other problems it is possible to prove similar claims quite easily (e.g. the probability that a random graph $G(n,p)$ has a clique of size $4$ is almost $1$ when $p(n) = \omega(n^{-2/3})$ and is almost $0$ when $p(n) = o(n^{-2/3})$, and it can be proven by a basic use of second moments).

However, for SAT I couldn’t find proofs. Do you know of any progress in this problem?

$\endgroup$
3
  • $\begingroup$ If you Google "phase transition SAT" you will find several papers, which should enable you to start a literature search to find some papers published on the theory. Have you tried doing a literature search from there? $\endgroup$ – D.W. Jun 2 '20 at 7:46
  • $\begingroup$ I did. However, the vast majority of the results I found were experimental (which I am not interested in), and I couldn't find recent theory papers considering this question $\endgroup$ – Dani Jun 2 '20 at 8:17
  • $\begingroup$ Well, did you find older theory papers? If so, please edit the question to summarize what you've found, and do a literature search starting from there (looking at newer papers that cite them). When I did a Google search, I immediately found a paper on the topic and it cited a theory paper, which ought to be enough to start a literature search. $\endgroup$ – D.W. Jun 2 '20 at 8:25
1
$\begingroup$

The two most relevant rigorous results are:

  1. Ehud Friedgut, Sharp thresholds of graph properties, and the $k$-SAT problem. This paper (with an appendix by Jean Bourgain) shows that $k$-SAT exhibits a sharp threshold. However, a priori this threshold could depend on $n$ (i.e., this method cannot show that $\alpha$ is constant).
  2. Jian Ding, Allan Sly, Nike Sun, Proof of the satisfiability conjecture for large $k$. The authors determine the exact value of $\alpha$ for $k \geq k_0$. This value of $\alpha$ had been calculated by physicists using the cavity method, but their arguments are not rigorous.

Related work discusses the geometry of the solution space of $k$-SAT around various thresholds. See for example Dimitris Achlioptas, Amin Coja-Oghlan, Federico Ricci-Tersenghi, On the solution‐space geometry of random constraint satisfaction problems.

$\endgroup$
4
  • $\begingroup$ thanks. If I understand correctly, seems that this problem is still open (I mean, a rigorous proof for $\alpha$ that does not depend on $n$ does not exist yet)? $\endgroup$ – Dani Jun 2 '20 at 8:20
  • $\begingroup$ Yes, for small $k$ I believe that it is still open. $\endgroup$ – Yuval Filmus Jun 2 '20 at 8:21
  • $\begingroup$ even for large $k$ - seems that the second paper you mentioned does not provide a rigorous claim, but rather uses statistical physics heuristics $\endgroup$ – Dani Jun 2 '20 at 8:22
  • $\begingroup$ That's absolutely false. The entire point of this paper is to provide rigorous proof for a formula that statistical physicists had known for decades. $\endgroup$ – Yuval Filmus Jun 2 '20 at 8:29

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.