Survey propagation: an algorithm for satisfiability

A. Braunstein, M. Mezard, R. Zecchina

We study the satisfiability of randomly generated formulas formed by $M$ clauses of exactly $K$ literals over $N$ Boolean variables. For a given value of $N$ the problem is known t…