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.
Preview
Unable to display preview. Download preview PDF.
References
D. Achlioptas and M. Molloy, “Almost all graphs with 2.522 n edges are not 3-colorable,” Manuscript, University of Toronto.
N. Alon, J.H. Spencer, and P. Erdös, The Probabilistic Method, J. Wiley, New York (1992).
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).
B. Bollobás, Random Graphs, Academic Press, London (1985).
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.
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.
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.
P. Cheeseman, B. Kanefsky and W. Taylor, “Where the really hard problems are,” Proceedings of IJCAI '91 (1991) 331–337.
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.
R. Dechter, “Constraint networks,” in S. Shapiro (ed.), Encyclopedia of Artificial Intelligence, Wiley, New York, 2nd ed. (1992) 276–285.
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.
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.
A. El Maftouhi and W. Fernandez de la Vega, “On random 3-SAT”, Combinatorics, Probability and Computing, Vol. 4 (1995) 189–195.
E. Friedgut, “Sharp thresholds for graph properties and the k-sat problem,” Manuscript in preparation.
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.
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.
T. Hogg, “Refining the phase transition in combinatorial search,” in [3], 127–154.
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.
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.
S. Kirkpatrick and B. Selman, “Critical behavior in the satisfiability of random Boolean expressions,” Science 264, pp 1297–1301, 1994.
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.
A.K. Mackworth, “Constraint satisfaction,” in S. Shapiro (ed.) Encyclopedia of Artificial Intelligence, Wiley, New York, 2nd ed. (1992) 285–293.
C. McDiarmid, “On a correlation inequality of Farr,” Combinatorics, Probability and Computing, Vol. 1 (1992) 157–160.
D. Mitchell, B. Selman, and H. Levesque, Generating hard satisfaability problems, Artificial Intelligence, Vol. 81 (1996), 17–29.
P. Prosser, “An empirical study of phase transitions in binary constraint satisfaction problems,” in [3], 81–109.
B.M. Smith and M.E. Dyer, “Locating the phase transition in binary constraint satisfaction problems,” in [3], 155–181.
J. H. Spencer, Ten Lectures on the Probabilistic Method, 2nd edition, SIAM, Philadelphia (1994).
D. Waltz, “Understanding line drawings of scenes with shadows,” The Psychology of Computer Vision, McGraw-Hill, New York (1975) 19–91.
C. Williams and T. Hogg, “Using deep structure to locate hard problems,” Proceedings of AAAI-92 (1992) 472–477.
C. Williams and T. Hogg, “Extending deep structure,” Proceedings of AAAI-93, (1993) 152–158.
C. Williams and T. Hogg, “Exploiting the deep structure of constraint problems,” Artificial Intelligence, Vol. 70 (1994) 73–117.
Author information
Authors and Affiliations
Editor information
Rights 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