Many hard examples in exact phase transitions. (English) Zbl 1088.68163

Summary: This paper analyzes the resolution complexity of two random Constraint Satisfaction Problem (CSP) models (i.e. Model RB/RD) for which we can establish the existence of phase transitions and identify the threshold points exactly. By encoding CSPs into CNF formulas, it is proved that almost all instances of Model RB/RD have no tree-like resolution proofs of less than exponential size. Thus, we not only introduce new families of CSPs and CNF formulas hard to solve, which can be useful in the experimental evaluation of CSP and SAT algorithms, but also propose models with both many hard instances and exact phase transitions. Finally, conclusions are presented, as well as a detailed comparison of Model RB/RD with the Hamiltonian cycle problem and random 3-SAT, which, respectively, exhibit three different kinds of phase transition behavior in NP-complete problems.


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] D. Achlioptas, L. Kirousis, E. Kranakis, D. Krizanc, Rigorous results for random (2+p)-SAT, in: Proc. of RALCOM-97, pp. 1-10. · Zbl 0992.68073
[2] Achlioptas, D.; Kirousis, L.M.; Kranakis, E.; Krizanc, D.; Molloy, M.S.; Stamatiou, Y.C., Random constraint satisfaction: a more accurate picture, (), 107-120 · Zbl 0984.68085
[3] Aldous, D.; Percus, A., Scaling and universality in continuous length combinatorial optimization, Proc. nat. acad. sci. USA, 100, 11211-11215, (2003) · Zbl 1063.90041
[4] P. Beame, R. Karp, T. Pitassi, M. Saks, On the complexity of unsatisfiability proofs for random k-CNF formulas, in: Proc. of STOC-98, pp. 561-571. · Zbl 1028.68067
[5] Beame, P.; Karp, R.; Pitassi, T.; Saks, M., The efficiency of resolution and Davis-Putnam procedures, SIAM J. comput., 31, 4, 1048-1075, (2002) · Zbl 1004.03048
[6] Ben-Sasson, E.; Wigderson, A., Short proofs are narrow—resolution made simple, J. ACM, 48, 2, 149-169, (2001) · Zbl 1089.03507
[7] Bollobás, B.; Fenner, T.I.; Frieze, A.M., An algorithm for finding Hamilton paths and cycles in random graphs, Combinatorica, 7, 4, 327-341, (1987) · Zbl 0638.05036
[8] V. Chvátal, B. Reed, Miks gets some (the odds are on his side), in: Proc. of the 33rd IEEE Symp. on Foundations of Comput. Sci. 1992, pp. 620-627. · Zbl 0977.68538
[9] Chvátal, V.; Szemerédi, E., Many hard examples for resolution, J. ACM, 35, 4, 208-759, (1988) · Zbl 0712.03008
[10] H. Connamacher, M. Molloy, The exact satisfiability threshold for a potentially intractable random constraint satisfaction problem, in: Proc. of FOCS 2004. · Zbl 1277.68217
[11] S. Cook, D. Mitchell, Finding hard instances of the satisfiability problem: a survey, in: Du, Gu, Pardalos (Eds.), Satisfiability Problem: Theory and Applications, DIMACS Ser. in Discrete Mathematics and Theoretical Computer Science, vol. 35, 1997. · Zbl 0889.68073
[12] Creignou, N.; Daudé, H., Combinatorial sharpness criterion and phase transition classification for random csps, Inform. comput., 190, 2, 220-238, (2004) · Zbl 1085.68151
[13] O. Dubois, J. Mandler, The 3-XORSAT threshold, in: Proc. FOCS 2002. · Zbl 1038.68052
[14] Dyer, M.; Frieze, A.; Molloy, M., A probabilistic analysis of randomly generated binary constraint satisfaction problems, Theoret. comput. sci., 290, 1815-1828, (2003) · Zbl 1055.68102
[15] A. Flaxman, A sharp threshold for a random constraint satisfaction problem, preprint. · Zbl 1121.68407
[16] Friedgut, E., Sharp thresholds of graph properties, and the k-sat problem. with an appendix by Jean Bourgain, J. amer. math. soc., 12, 1017-1054, (1999) · Zbl 0932.05084
[17] A. Frieze, M. Molloy, The satisfiability threshold for randomly generated binary constraint satisfaction problems, in: Proc. of RANDOM-03, 2003. · Zbl 1279.68302
[18] A.M. Frieze, N.C. Wormald, Random k-SAT: a tight threshold for moderately growing k, in: Proc. of the Fifth Internat. Symp. on Theory and Appl. of Satisfiability Testing, 2002, pp. 1-6. · Zbl 1083.68048
[19] Y. Gao, J. Culberson, Resolution complexity of random constraint satisfaction problems: another half of the story, in: Proc. LICS-03, Workshop on Typical Case Complexity and Phase Transitions, Ottawa, Canada, June 2003. · Zbl 1179.68142
[20] Gent, I.P.; MacIntyre, E.; Prosser, P.; Smith, B.M.; Walsh, T., Random constraint satisfaction: flaws and structures, J. constraints, 6, 4, 345-372, (2001) · Zbl 0992.68193
[21] A. Goerdt, A threshold for unsatisfiability, in: 17th Internat. Symp. of Math. Foundations of Comput. Sci., Lecture Notes in Computer Science, vol. 629, Springer, Berlin, 1992, pp. 264-275.
[22] Komlós, M.; Szemerédi, E., Limit distribution for the existence of a Hamilton cycle in a random graph, Discrete math., 43, 55-63, (1983) · Zbl 0521.05055
[23] D. Mitchell, Resolution complexity of random constraints, in: Proc. CP 2002, Lecture Notes in Computer Science, vol. 2470, pp. 295-309.
[24] D. Mitchell, B. Selman, H. Levesque, Hard and easy distributions of sat problems, in: Proc. 10th Nat. Conf. on Artificial Intelligence (AAAI-92), 1992, pp. 459-465.
[25] M. Molloy, Models for random constraint satisfaction problems, Conference version, in: Proc. of STOC 2002, submitted. · Zbl 1029.68118
[26] M. Molloy, M. Salavatipour, The resolution complexity of random constraint satisfaction problems, in: Proc. FOCS-03, 2003. · Zbl 1139.68028
[27] Monasson, R.; Zecchina, R.; Kirkpatrick, S.; Selman, B.; Troyansky, L., Phase transition and search cost in the \(2 + p \text{-SAT}\) problem, (), (PhysComp96)
[28] Monasson, R.; Zecchina, R.; Kirkpatrick, S.; Selman, B.; Troyansky, L., Determining computational complexity from characteristic phase transitions, Nature, 400, 8, 133-137, (1999) · Zbl 1369.68244
[29] Smith, B.M., Constructing an asymptotic phase transition in random binary constraint satisfaction problems, Theoret. comput. sci., 265, 265-283, (2001), (Special Issue on NP-Hardness and Phase Transitions) · Zbl 0992.68191
[30] Vandegriend, B.; Culberson, J., The \(G_{n, m}\) phase transition is not hard for the Hamiltonian cycle problem, J. artif. intell. res., 9, 219-245, (1998) · Zbl 0910.68085
[31] Xu, K.; Boussemart, F.; Hemery, F.; Lecoutre, C., A simple model to generate hard satisfiable instances, (), 337-342
[32] Xu, K.; Li, W., Exact phase transitions in random constraint satisfaction problems, J. artif. intell. res., 12, 93-103, (2000) · Zbl 0940.68099
[33] Xu, K.; Li, W., On the average similarity degree between solutions of random k-SAT and random csps, Discrete appl. math., 136, 125-149, (2004) · Zbl 1074.68025
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.