Groupe d’études et de recherche en analyse des décisions

G-98-68

Local Optima Topology for the 3-SAT Problem

, et

We study empirically the topology of the local minima of the 3-SAT problem. In particular, we analyze the size of the plateaus, their altitude, their attraction, as well as their number of exits. It has been observed that the most difficult 3-SAT problems are those for which the ratio of the number of variables over the number of clauses is roughly 4.3. The difference between the easy and the difficult problems is clearly illustrated by this topological study.

, 14 pages