iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/BFb0017433
Random constraint satisfaction: A more accurate picture | SpringerLink
Skip to main content
Springer Nature Link
Log in

Random constraint satisfaction: A more accurate picture

  • Session 2b
  • Conference paper
  • First Online:
Principles and Practice of Constraint Programming-CP97 (CP 1997)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1330))

  • 165 Accesses

Abstract

Recently there has been a great amount of interest in Random Constraint Satisfaction Problems, both from an experimental and a theoretical point of view. Rather intriguingly, experimental results with various models for generating random CSP instances suggest a “threshold-like” behavior and some theoretical work has been done in analyzing these models when the number of variables becomes large (asymptotic). In this paper we prove that the models commonly used for generating random CSP instances do not have an asymptotic threshold. In particular, we prove that as the number of variables becomes large, almost add instances they generate are trivially overconstrained. We then present a new model for random CSP and, in the spirit of random k-SAT, we derive lower and upper bounds for its parameters so that instances are “almost surely” underconstrained and overconstrained, respectively. Finally, for the case of one of the popular models in Artificial Intelligence we derive sharper estimates for the probability of being overconstrained, as a function of the number of variables. Canada PGS B Scholarship. E-mail: optas@cs.toronto.edu

Partially supported by the EU ESPRIT Long-term Research Project ALCOM-IT (Project Nr. 20244).

Supported in part by an NSERC grant.

Partially supported by the EU ESPRIT Long-term Research Project ALCOM-IT (Project Nr. 20244).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. D. Achlioptas and M. Molloy, “Almost all graphs with 2.522 n edges are not 3-colorable,” Manuscript, University of Toronto.

    Google Scholar 

  2. N. Alon, J.H. Spencer, and P. Erdös, The Probabilistic Method, J. Wiley, New York (1992).

    Google Scholar 

  3. D.G. Bobrow and M. Brady, eds., Special Volume on Frontiers in Problem Solving: Phase Transitions and Complexity, Guest editors: T. Hogg, B.A. Hubermann, and C.P. Williams, Artificial Intelligence, Vol. 81, Numbers 1–2 (1996).

    Google Scholar 

  4. B. Bollobás, Random Graphs, Academic Press, London (1985).

    Google Scholar 

  5. A.Z. Broder, A.M. Frieze, and E. Upfal, “On the satisfiability and maximum satisfiability of random 3-CNF formulas,” Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (1993) 322‐330.

    Google Scholar 

  6. M.-T. Chao and J. Franco, “Probabilistic analysis of two heuristics for the 3-satisfiability problem,” SIAM Journal on Computing, Vol. 15 (1986) 1106–1118.

    Google Scholar 

  7. M.-T. Chao and J. Franco, “Probabilistic analysis of a generalization of the unitclause literal selection heuristic for the k-satisfiability problem,” Information Science, Vol. 51 (1990) 289–314.

    Google Scholar 

  8. P. Cheeseman, B. Kanefsky and W. Taylor, “Where the really hard problems are,” Proceedings of IJCAI '91 (1991) 331–337.

    Google Scholar 

  9. V. Chvátal and B. Reed, “Mick gets some (the odds are on his side),” in Proceedings of 33rd IEEE Symposium on Foundations of Computer Science (1992) 620–627.

    Google Scholar 

  10. R. Dechter, “Constraint networks,” in S. Shapiro (ed.), Encyclopedia of Artificial Intelligence, Wiley, New York, 2nd ed. (1992) 276–285.

    Google Scholar 

  11. O. Dubois and Y. Boufkhad, A General Upper Bound for the Satisfiability Threshold of Random r-SAT Formulae, Preprint, LAFORIA, CNRS-Université Paris 6, 1996.

    Google Scholar 

  12. P. Erdös and A. Rényi, “On the evolution of random graphs,” Publ. of the Math. Inst. of the Hung. Acad. Sci., Vol. 5 (1960) 17–61.

    Google Scholar 

  13. A. El Maftouhi and W. Fernandez de la Vega, “On random 3-SAT”, Combinatorics, Probability and Computing, Vol. 4 (1995) 189–195.

    Google Scholar 

  14. E. Friedgut, “Sharp thresholds for graph properties and the k-sat problem,” Manuscript in preparation.

    Google Scholar 

  15. A. Frieze and S. Suen, “Analysis of two simple heuristics on a random instance of k-SAT,” Journal of Algorithms, Vol. 20 (1996) 312–355.

    Google Scholar 

  16. A. Goerdt, “A threshold for satisfiability,” in I.M. Haven and V. Koubek (eds.) Proceedings of the Symposium on the Mathematical Foundations of Computer Science (1992) 264–274.

    Google Scholar 

  17. T. Hogg, “Refining the phase transition in combinatorial search,” in [3], 127–154.

    Google Scholar 

  18. J. Kahn, G. Kalai, and N. Linial, “The influence of variables on Boolean functions”, Proceedings of the 29th Annual Symposium on the Foundations of Computer Science (1988) 68–80.

    Google Scholar 

  19. A. Kamath, R. Motwani, K. Palem, and P. Spirakis, “Tail bounds for occupancy and the satisfiability threshold conjecture,” Random Structures and Algorithms, Vol. 7 (1995) 59–80.

    Google Scholar 

  20. S. Kirkpatrick and B. Selman, “Critical behavior in the satisfiability of random Boolean expressions,” Science 264, pp 1297–1301, 1994.

    Google Scholar 

  21. L. M. Kirousis, E. Kranakis, and D. Krizanc, “Approximating the unsatisfiability threshold of random formulas,” Proceedings of the Fourth Annual European Symposium on Algorithms, ESA '96, (1996) 27–38.

    Google Scholar 

  22. A.K. Mackworth, “Constraint satisfaction,” in S. Shapiro (ed.) Encyclopedia of Artificial Intelligence, Wiley, New York, 2nd ed. (1992) 285–293.

    Google Scholar 

  23. C. McDiarmid, “On a correlation inequality of Farr,” Combinatorics, Probability and Computing, Vol. 1 (1992) 157–160.

    Google Scholar 

  24. D. Mitchell, B. Selman, and H. Levesque, Generating hard satisfaability problems, Artificial Intelligence, Vol. 81 (1996), 17–29.

    Google Scholar 

  25. P. Prosser, “An empirical study of phase transitions in binary constraint satisfaction problems,” in [3], 81–109.

    Google Scholar 

  26. B.M. Smith and M.E. Dyer, “Locating the phase transition in binary constraint satisfaction problems,” in [3], 155–181.

    Google Scholar 

  27. J. H. Spencer, Ten Lectures on the Probabilistic Method, 2nd edition, SIAM, Philadelphia (1994).

    Google Scholar 

  28. D. Waltz, “Understanding line drawings of scenes with shadows,” The Psychology of Computer Vision, McGraw-Hill, New York (1975) 19–91.

    Google Scholar 

  29. C. Williams and T. Hogg, “Using deep structure to locate hard problems,” Proceedings of AAAI-92 (1992) 472–477.

    Google Scholar 

  30. C. Williams and T. Hogg, “Extending deep structure,” Proceedings of AAAI-93, (1993) 152–158.

    Google Scholar 

  31. C. Williams and T. Hogg, “Exploiting the deep structure of constraint problems,” Artificial Intelligence, Vol. 70 (1994) 73–117.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Toronto, M5S 3G4, Toronto, ON, Canada

    Dimitris Achlioptas & Michael S. O. Molloy

  2. Department of Computer Engineering and Informatics, University of Patras, Rio, 26500, Patras, Greece

    Lefteris M. Kirousis & Yannis C. Stamatiou

  3. School of Computer Science, Carleton University, K1S 51B6, Ottawa, ON, Canada

    Evangelos Kranakis & Danny Krizanc

Authors
  1. Dimitris Achlioptas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lefteris M. Kirousis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Evangelos Kranakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Danny Krizanc
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Michael S. O. Molloy
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Yannis C. Stamatiou
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Gert Smolka

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Achlioptas, D., Kirousis, L.M., Kranakis, E., Krizanc, D., Molloy, M.S.O., Stamatiou, Y.C. (1997). Random constraint satisfaction: A more accurate picture. In: Smolka, G. (eds) Principles and Practice of Constraint Programming-CP97. CP 1997. Lecture Notes in Computer Science, vol 1330. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0017433

Download citation

  • DOI: https://doi.org/10.1007/BFb0017433

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63753-0

  • Online ISBN: 978-3-540-69642-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation