Random K-satisfiability
Marc Mézard, Andrea Montanari · 2009
Abstract This chapter studies an ensemble of random satisfiability problems, ‘random K-satisfiability’ (K-SAT). Applying the 1RSB cavity method, it first derives the phase diagram in the limit of large N, in particular the location of the SAT-UNSAT threshold. Within the SAT phase, the chapter focuses on the intermediate clustered phase close, and computes the number of clusters to leading exponential order in N. The application of survey propagation to this problem is then described. Combined with a simple decimation procedure, the chapter provides an efficient method for finding satisfiable assignments in the clustered phase. The whole chapter is based on heuristic arguments. There is not yet any rigorous proof of the results presented, neither concerning the phase diagram, nor the convergence properties of message passing algorithms and their use in decimation procedures.