The asymptotic \(k\)-SAT threshold (Q900872)

This paper considers the satisfiability of random boolean formulae in conjunctive normal form, which have \(m\) clauses with \(k\) literals on \(n\) variables. An assignment of truth values to each one of the \(n\) variables satisfies the formula, if in every clause there is at least one TRUE literal. The problem of determining whether a given formula has a satisfying truth assignment is the well-known \(k\)-SAT problem. Here, a formula is formed by selecting \(m=cn\) clauses uniformly at random among all clauses with \(k\) literals. Physicists have predicted that there is a critical value \(c(k)\) such that when \(c\) crosses \(c(k)\) (from the left) the probability of satisfiability jumps from \(1-o(1)\) to \(o(1)\) (or, asymptotically from 1 to 0). The value of \(c_k\) has been predicted up to an additive term that tends to 0 as \(k \to \infty\). The authors confirm this prediction and they actually bound the aforementioned additive error term by a function that decays exponentially in \(k\). The proof of this is based on a second moment argument of a special type. The difficulty here lies on a fundamental asymmetry of the \(k\)-SAT problem: any two satisfying truth assignments are heavily correlated. In fact, a satisfying truth assignment tends to look like a special truth assignment which maximises the number of TRUE literals in the formula. Thus, a plain second moment argument does not quite work. Correlation is particularly strong in the range of \(c\) where condensation occurs: there is a cluster of satisfying truth assignments which contains an asymptotically positive fraction of the entire set of satisfying truth assignments and contains satisfying truth assignments which share large part with other truth assignments in this cluster. This problem is circumvented by considering the notion of a cover of a formula. Roughly speaking, this is a partial truth assignment such that if it satisfies a clause then the corresponding literal which is TRUE is effectively frozen but if it is undetermined there are at least two literals whose value is undetermined. A second moment argument is then performed on the number of covers of the random formula. This is done using a random variable which incorporates the drift of the cover towards the assignment which majorisies the number of TRUE literals in the formula.