Abstract:
We study the satisfiability of random Boolean expressions built from many clauses with 3 variables per clause, the 3-SAT problem. The 3-SAT problem is known to be an NP-complete problem and detailed knowledge of its energy landscape is of central importance in the field of combinatorial optimisation.
The 3-SAT expressions with a ratio of clauses to variables less than a certain threshold are almost always satisfiable, whereas those with the ratio above this threshold are generally unsatisfiable. We observe furthermore the existence of an intermediate phase in the satisfiable region, where the proliferation of metastable states is at the origin of the slowdown of local search algorithms.
To picture this phase, we focus on the optimisation version of the random 3-SAT problem, the MAX-3-SAT problem, and we study the performance of the finite energy version of the survey propagation algorithm. We show that a simple decimation strategy is sufficient to reach configurations well below the lower bound for the dynamic threshold energy (metastable states) and very close to the analytic prediction for the optimal ground states.