Models and thresholds for random constraint satisfaction problems. (English) Zbl 1192.68652
Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002. New York, NY: ACM Press (ISBN 1-581-13495-9). 209-217, electronic only (2002).
For the entire collection see [Zbl 1074.68502].
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
References:
| [1] | D. Achlioptas. Threshold Phenomena in Random Graph Colouring and Satisfiability. Ph.D. Thesis, Dept. of Computer Science, University of Toronto, 1999. |
| [2] | D. Achlioptas. Personal communication. |
| [3] | D. Achlioptas, P. Beame and M. Molloy. A sharp threshold in proof complexity. Proceedings of STOC 2001, 337-346. 10.1145/380752.380820 · Zbl 1323.03088 |
| [4] | D. Aclioptas and E. Friedgut. A threshold for k-colourability. Random Structures and Algorithms 14 (1999), 63-70. 10.1002/(SICI)1098-2418(1999010)14:1 · Zbl 0962.05055 |
| [5] | D. Achlioptas, L. Kirousis, E. Kranakis, D. Krizanc. Rigorous results for random (2+p)-SAT. |
| [6] | D. Achlioptas, L. Kirousis, E. Kranakis, D. Krizanc, M. Molloy, and Y. Stamatiou. Random constraint satisfaction: a more accurate picture. Constraints 6, 329-324 (2001). Conference version in Proceedings of CP 97, 107-120. 10.1023/A:1011402324562 · Zbl 0984.68085 |
| [7] | N. Alon and J. Spencer, The Probabilistic Method. Wiley (1992). · Zbl 0767.05001 |
| [8] | B. Bollobas. Random Graphs. Academic Press (1985). · Zbl 0567.05042 |
| [9] | P. Cheeseman, B. Kanefsky and W.M. Taylor. Where the really hard problems are. Proceedings of the 12th IJCAI (1991), 331-337. · Zbl 0747.68064 |
| [10] | V. Chvatal and E. Szemeredi. Many hard examples for resolution. Journal of the ACM 35 (1988) 759-768. 10.1145/48014.48016 · Zbl 0712.03008 |
| [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. · Zbl 0103.16301 |
| [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. · Zbl 0932.05084 |
| [13] | E. Friedgut. Personal communication. |
| [14] | I. Gent, E. MacIntyre, P. Prosser, B. Smith and T. Walsh. Random constraint satisfaction: flaws and structure. Constraints 6, 345-372 (2001). 10.1023/A:1011454308633 · Zbl 0992.68193 |
| [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. · Zbl 0712.68076 |
| [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. · Zbl 1523.68093 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
