Models and thresholds for random constraint satisfaction problems

ABSTRACT

We introduce a class of models for random Constraint Satisfaction Problems. This class includes and generalizes many previously studied models. We characterize those models from our class which exhibit thresholds for satisfiability in the sense that the limiting probability of satisfiability changes significantly as the number of constraints increases. We also discuss models which exhibit sharp thresholds in the sense that the limiting probability jumps from 0 to 1 suddenly.

REFERENCES

• 1: Demetrios Achlioptas , Allan Borodin , Michael Molloy, Threshold phenomena in random graph colouring and satisfiability, 1999
• 2: D. Achlioptas. Personal communication.
• 3: Dimitris Achlioptas , Paul Beame , Michael Molloy, A sharp threshold in proof complexity, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.337-346, July 2001, Hersonissos, Greece [doi>10.1145/380752.380820]
• 4: Dimitris Achlioptas , Ehud Friedgut, A sharp threshold for k-colorability, Random Structures & Algorithms, v.14 n.1, p.63-70, Jan. 1999 [doi>10.1002/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7]
• 5: D. Achlioptas, L. Kirousis, E. Kranakis, D. Krizanc. Rigorous results for random (2+p)-SAT.} Proceedings of RALCOM '97 (1997), 14--23.
• 6: Dimitris Achlioptas , Michael S. O. Molloy , Lefteris M. Kirousis , Yannis C. Stamatiou , Evangelos Kranakis , Danny Krizanc, Random Constraint Satisfaction: A More Accurate Picture, Constraints, v.6 n.4, p.329-344, October 2001 [doi>10.1023/A:1011402324562]
• 7: N. Alon and J. Spencer, The Probabilistic Method. Wiley (1992).
• 8: B. Bollobas. Random Graphs. Academic Press (1985).
• 9: P. Cheeseman, B. Kanefsky and W.M. Taylor. Where the really hard problems are. Proceedings of the 12th IJCAI (1991), 331--337.
• 10: Vašek Chvátal , Endre Szemerédi, Many hard examples for resolution, Journal of the ACM (JACM), v.35 n.4, p.759-768, Oct. 1988 [doi>10.1145/48014.48016]
• 11: P. Erdos and A. Renyi. On the evolution of random graphs. Publication of the (MATH)ematical Institute of the Hungarian Academy of Sciences, 5 (1960), 17--61.
• 12: E. Friedgut and an appendix by J. Bourgain. Sharp thresholds of graph properties and the k-SAT problem. J. Am. (MATH). Soc. 12 (1999), 1017--1054.
• 13: E. Friedgut. Personal communication.
• 14: Ian P. Gent , Ewan Macintyre , Patrick Prosser , Barbara M. Smith , Toby Walsh, Random Constraint Satisfaction: Flaws and Structure, Constraints, v.6 n.4, p.345-372, October 2001 [doi>10.1023/A:1011454308633]
• 15: S. Grant and B.M. Smith. The phase transition behaviour of maintaining arc consistency. Proceedings of ECAI-96, 175--179.
• 16: R. Karp. The transitive closure of a random digraph. Random Structures and Algorithms 1 (1990), 73--93.
• 17: A. Meisels, S.E. Shimony and G. Solotorevsky. Bayes networks for estimating the number of solutions to a CSP. Proceedings of AAAI-97 179--184.
• 18: D. Mitchell, B. Selman and H. Levesque. Hard and easy distributions of SAT problems Proceedings of AAAI-92, 459--465.
• 19: P. Prosser. An empirical study of phase transitions in binary constraint satisfaction problems. Artificial Intelligence 81 (1996), 81--109.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Theory

Keywords:
sharp thresholds