Constraint satisfaction: random regulark-SAT
Amin Coja‐Oghlan · 2015
Abstract This chapter discusses the random regular k-SAT problem, i.e., a random k-CNF formula Φ = Φk(n,d) on n variables such that each of the 2n literals appears exactly d times. With k0 a certain constant, for any k > k0 a number dk is identified such that for any d ≤ dk the random formula Φ admits a truth assignment that satisfies all but o(n) clauses with high probability, whereas for d > dk there is with high probability no such truth assignment. This phase transition is consistent with predictions based on the cavity method from statistical mechanics, and the proof also directly employs ideas from the cavity method, such as the notion of covers (relaxed satisfying assignments), which are obtained here via a whitening process.