On the solution-space geometry of random constraint satisfaction problems

ABSTRACT

For a number of random constraint satisfaction problems, such as random k-SAT and random graph/hypergraph coloring, there are very good estimates of the largest constraint density for which solutions exist. Yet, all known polynomial-time algorithms for these problems fail to find solutions even at much lower densities. To understand the origin of this gap we study how the structure of the space of solutions evolves in such problems as constraints are added. In particular, we prove that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters. Moreover, inside each cluster most variables are frozen, i.e., take only one value. The existence of such frozen variables gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. At the same time, our results establish rigorously one of the two main hypotheses underlying Survey Propagation, a heuristic introduced by physicists in recent years that appears to perform extraordinarily well on random constraint satisfaction problems.

REFERENCES

• 1: D. Achlioptas, J. Thorpe, manuscript.
• 2: Dimitris Achlioptas , Cristopher Moore, The Asymptotic Order of the Random k -SAT Threshold, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.779-788, November 16-19, 2002
• 3: D. Achlioptas, A. Naor, The two possible values of the chromatic number of a random graph, Annals of Mathematics, 162 (3) (2005), 1333--1349.
• 4: D. Achlioptas, A. Naor, and Y. Peres, Rigorous location of phase transitions in hard optimization problems, Nature, 435, June 9th 2005, 759--764.
• 5: D. Achlioptas, Y. Peres, The threshold for random k-SAT is 2k ln 2 - O(k), Journal of American Mathematical Society, 17 (2004), 947--973.
• 6: S. Aji, R.J. McEliece, The Generalized Distributive Law, IEEE Trans. Inform. Theory, 46 (2000), 325--343.
• 7: Mikhail Alekhnovich , Eli Ben-Sasson, Linear Upper Bounds for Random Walk on Small Density Random 3-CNF, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.352, October 11-14, 2003
• 8: A. Braunstein, R. Zecchina, Survey propagation as local equilibrium equations, J. Stat. Mech., (2004), P06007.
• 9: Ming-Te Chao , John Franco, Probabilistic analysis of two heuristics for the 3-satisfiability problem, SIAM Journal on Computing, v.15 n.4, p.1106-1118, Nov. 1986 [doi>10.1137/0215080]
• 10: V. Chvátal, B. Reed. Mick gets some (the odds are on his side), In Proc. 33th STOC, 620--627, 1992.
• 11: O. Dubois , Y. Boufkhad, A general upper bound for the satisfiability threshold of random r-SAT formulae, Journal of Algorithms, v.24 n.2, p.395-420, Aug. 1997 [doi>10.1006/jagm.1997.0867]
• 12: O. Dubois, Y. Boufkhad, and J. Mandler. Typical random 3-SAT formulae and the satisfiability threshold, Electronic Colloquium on Computational Complexity, 10 (2003).
• 13: E. Friedgut, personal communication.
• 14: Alan Frieze , Stephen Suen, Analysis of two simple heuristics on a random instance of k-SAT, Journal of Algorithms, v.20 n.2, p.312-355, March 1996 [doi>10.1006/jagm.1996.0016]
• 15: Anil Kamath , Rajeev Motwani , Paul Spirakis , Krishna Palem, Tail bounds for occupancy and the satisfiability threshold conjecture, Random Structures & Algorithms, v.7 n.1, p.59-80, Aug. 1995 [doi>10.1002/rsa.3240070105]
• 16: Alexis C. Kaporis , Lefteris M. Kirousis , Efthimios G. Lalas, The Probabilistic Analysis of a Greedy Satisfiability Algorithm, Proceedings of the 10th Annual European Symposium on Algorithms, p.574-585, September 17-21, 2002
• 17: A. Kaporis, L. M. Kirousis, and E. G. Lalas. Selecting complementary pairs of literals, In Proc. LICS '03 workshop on Typical Case Complexity and Phase Transitions, 2003.
• 18: Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Yannis C. Stamatiou, Approximating the unsatisfiability threshold of random formulas, Random Structures & Algorithms, v.12 n.3, p.253-269, May 1998 [doi>10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U]
• 19: Elitza Maneva , Elchanan Mossel , Martin J. Wainwright, A new look at survey propagation and its generalizations, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 20: M. Mézard, T. Mora, and R. Zecchina, Clustering of Solutions in the Random Satisfiability Problem, Phys. Rev. Lett. 94 (2005), 197205. Also, cond-mat/0504070.
• 21: M. Mézard, T. Mora, and R. Zecchina, Pairs of SAT Assignments and Clustering in Random Boolean Formulae, cond-mat/0506053, June 2nd 2005.
• 22: M. Mézard, G. Parisi, and R. Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems, Science 297 (2002), 812--815.
• 23: N. C. Wormald, Differential equations for random processes and random graphs, Ann. App. Prob. , 5 (1995), 1217--1235.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Algorithms, Theory

Keywords:
random formulas, satisfiability, survey propagation