Constructing an asymptotic phase transition in random binary constraint satisfaction problems. (English) Zbl 0992.68191

Summary: The standard models used to generate random binary constraint satisfaction problems are described. At the problem sizes studied experimentally, a phase transition is seen as the constraint tightness is varied. However, D. Achlioptas, L. M. Kirousis, E. Kranakis, D. Krizanc, M. S. O. Molloy and Y. C. Stamatiou [Lect. Notes Comput. Sci. 1330, 107-120 (1997)] showed that if the problem size (number of variables) increases while the remaining parameters are kept constant, asymptotically almost all instances are unsatisfiable. In this paper, an alternative scheme for one of the standard models is proposed in which both the number of values in each variable’s domain and the average degree of the constraint graph are increased with problem size. It is shown that with this scheme there is asymptotically a range of values of the constraint tightness in which instances are trivially satisfiable with probability at least 0.5 and a range in which instances are almost all unsatisfiable; hence there is a crossover point at some value of the constraint tightness between these two ranges. This scheme is compared to a similar scheme due to Xu and Li.


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI


[1] D. Achlioptas, Lower bounds for random 3-SAT via differential equations, Theoret. Comput. Sci. 265 (this vol.) (2001) 159-185. · Zbl 0983.68079
[2] Achlioptas, D.; Kirousis, L.M.; Kranakis, E.; Krizanc, D.; Molloy, M.S.O.; Stamatiou, Y.C., Random constraint satisfaction—a more accurate picture, (), 107-120
[3] P. Cheeseman, B. Kanefsky, W. Taylor, Where the really hard problems are, in: Proc. IJCAI-91, Vol. 1, 1991, pp. 331-337. · Zbl 0747.68064
[4] J. Franco, Results related to threshold phenomena research in satisfiability: lower bounds, Theoret. Comput. Sci. 265 (this vol.) (2001) 147-157. · Zbl 0983.68081
[5] Freuder, E.C., A sufficient condition for backtrack-free search, J. ACM, 29, 24-32, (1982) · Zbl 0477.68063
[6] D. Frost, R. Dechter, In search of the best constraint satisfaction search, in: Proc. AAAI’94, 1994, pp. 301-306.
[7] I. Gent, E. MacIntyre, P. Prosser, B. Smith, T. Walsh, Random constraint satisfaction: flaws and structure, Research Report 98.23, School of Computer Studies, University of Leeds, 1998. (Revised following reviewers’ comments for Constraints). · Zbl 0992.68193
[8] Gomes, C.P.; Selman, B.; Crato, N., Heavy-tailed distributions in combinatorial search, (), 121-135
[9] S.A. Grant, B.M. Smith, The phase transition behaviour of maintaining arc consistency, Research Report 95.25, School of Computer Studies, University of Leeds, September, 1995.
[10] S.A. Grant, B.M. Smith, The phase transition behaviour of maintaining arc consistency, in: W. Wahlster (Ed.), Proc. ECAI’96, 1996, pp. 175-179.
[11] Haralick, R.; Elliott, G., Increasing tree search efficiency for constraint satisfaction problems, Artificial intelligence, 14, 263-313, (1980)
[12] Hogg, T.; Williams, C.P., The hardest constraint problems: a double phase transition, Artificial intelligence, 69, 359-377, (1994) · Zbl 0938.68826
[13] MacIntyre, E.; Prosser, P.; Smith, B.; Walsh, T., Random constraint satisfaction: theory meets practice, (), 325-339
[14] Pittel, B.; Spencer, J.; Wormald, N., Sudden emergence of a giant \(k\)-core in a random graph, J. combin. theory (B), 67, 111-151, (1996) · Zbl 0860.05065
[15] Prosser, P., An empirical study of phase transitions in binary constraint satisfaction problems, Artificial intelligence, 81, 81-109, (1996)
[16] B.M. Smith, M.E. Dyer, Locating the phase transition in constraint satisfaction problems, Artificial Intelligence 81 \((1996)\) 155-181. (Special Issue on Frontiers in Problem Solving: Phase Transitions and Complexity.)
[17] Smith, B.M.; Grant, S.A., Modelling exceptionally hard constraint satisfaction problems., (), 182-195
[18] Williams, C.; Hogg, T., Exploiting the deep structure of constraint problems, Artificial intelligence, 70, 73-117, (1994) · Zbl 0938.68827
[19] Xu, K.; Li, W., Exact phase transitions in random constraint satisfaction problems, J. AI res., 12, 93-103, (2000) · Zbl 0940.68099
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.