×

A general model and thresholds for random constraint satisfaction problems. (English) Zbl 1270.68267

Summary: We study the relation among the parameters in their most general setting that define a large class of random CSP models \(d\)-\(k\)-CSP where \(d\) is the domain size and \(k\) is the length of the constraint scopes. The model \(d\)-\(k\)-CSP unifies several related models such as the model RB and the model \(k\)-CSP. We prove that the model \(d\)-\(k\)-CSP exhibits exact phase transitions if \(k\ln d\) increases no slower than the logarithm of the number of variables. A series of experimental studies with interesting observations are carried out to illustrate the solubility phase transition and the hardness of instances around phase transitions.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q25 Analysis of algorithms and problem complexity
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Achlioptas, D.; Kirousis, L.; Kranakis, E.; Krizanc, D.; Molloy, M.; Stamatiou, Y., Random constraint satisfaction: A more accurate picture, (Proceedings of the Third International Conference on Principles and Practice of Constraint Programming. Proceedings of the Third International Conference on Principles and Practice of Constraint Programming, LNCS, vol. 1330 (1997), Springer), 107-120
[2] Ben-Sasson, E.; Wigderson, A., Short proofs are narrow - resolution made simple, Journal of the ACM, 48, 149-169 (2001) · Zbl 1089.03507
[3] Cheesman, P.; Kanefsky, B.; Taylor, W., Where the really hard problems are, (Proceedings of IJCAI-91 (1991), IJCAII), 331-337 · Zbl 0747.68064
[4] Chvátal, V.; Reed, B., Miks gets some (the odds are on his side), (Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science (1992), IEEE Computer Society Press), 620-627 · Zbl 0977.68538
[5] Chvátal, V.; Szemerédi, E., Many hard examples for resolution, Journal of the ACM, 35, 208-759 (1988) · Zbl 0712.03008
[6] Creignou, N.; Daudé, H., Random generalized satisfiability problems, (Proceedings of SAT (2002), Elsevier) · Zbl 1182.68232
[7] Creignou, N.; Daudé, H., Generalized satisfiability problems: minimal elements and phase transitions, Theoretical Computer Science, 302, 417-430 (2003) · Zbl 1051.68075
[8] Creignou, N.; Daudé, H., Combinatorial sharpness criterion and phase transition classification for random CSPs, Information and Computation, 190, 220-238 (2004) · Zbl 1085.68151
[9] Díaz, J.; Kirousis, L.; Mitsche, D.; Pérez-Giménez, X., On the satisfiability threshold of formulas with three literals per clause, Theoretical Computer Science, 410, 2920-2934 (2009) · Zbl 1173.68025
[10] Dyer, M.; Frieze, A.; Molloy, M., A probabilistic analysis of randomly generated binary constraint satisfaction problems, Theoretical Computer Science, 290, 1815-1828 (2003) · Zbl 1055.68102
[11] Fan, Y.; Shen, J., On the phase transitions of random \(k\)-constraint satisfaction problems, Artificial Intelligence, 175, 914-927 (2011) · Zbl 1216.68243
[12] Flaxman, A., A sharp threshold for a random constraint satisfaction problem, Discrete Mathematics, 285, 301-305 (2004) · Zbl 1121.68407
[13] Friedgut, E., Sharp thresholds of graph properties, and the \(k\)-sat problem, Journal of the American Mathematical Society, 12, 1017-1054 (1999), with an appendix by Jean Bourgain · Zbl 0932.05084
[14] Frieze, A.; Molloy, M., The satisfiability threshold for randomly generated binary constraint satisfaction problems, Random Structures & Algorithms, 28, 323-339 (2006) · Zbl 1094.68092
[15] Frieze, A.; Suen, S., Analysis of two simple heuristics on a random instance of \(k\)-sat, Journal of Algorithms, 20, 312-355 (1996) · Zbl 0852.68038
[16] Frieze, A.; Wormald, N., Random \(k\)-sat: A tight threshold for moderately growing \(k\), (Proceedings of the Fifth International Symposium on Theory and Applications of Satisfiability Testing (2002), Springer), 1-6 · Zbl 1083.68048
[17] Gao, Y.; Culberson, J., Consistency and random constraint satisfaction models with a high constraint tightness, (Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP-2004) (2004), Springer), 17-31 · Zbl 1152.68552
[18] Gao, Y.; Culberson, J., Consistency and random constraint satisfaction models, Journal of Artificial Intelligence Research, 28, 517-557 (2007) · Zbl 1182.68239
[19] Gent, I.; Macintyre, E.; Prosser, P.; Smith, B., Random constraint satisfaction: Flaws and structure, Constraints, 6, 345-372 (2001) · Zbl 0992.68193
[20] Jiang, W.; Liu, T.; Ren, T.; Xu, K., Two hardness results on feedback vertex sets, (Frontiers in Algorithmics and Algorithmic Aspects in Information and Management—Joint International Conference (FAW-AAIM) (2011), Springer), 233-243 · Zbl 1329.68125
[21] Kaporis, A.; Kirousis, L.; Lalas, E., The probabilistic analysis of a greedy satisfiability algorithm, (The 10th Annual European Symposium on Algorithms (2002), Springer), 574-585 · Zbl 1019.68814
[22] Liu, T.; Lin, X.; Wang, C.; Su, K.; Xu, K., Large hinge width on sparse random hypergraphs, (Proceedings of the 22nd International Joint Conference on Artificial Intelligence (2011), IJCAI/AAAI), 611-616
[23] Mitzenmacher, M.; Upfal, E., Probability and Computing: Randomized Algorithm and Probabilistic Analysis (2005), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 1092.60001
[24] Molloy, M., Models and thresholds for random constraint satisfaction problems, (Proceedings of the 34th ACM Symposium on Theory of Computing (2001), ACM Press), 209-217 · Zbl 1192.68652
[25] Molloy, M.; Salavatipour, M., The resolution complexity of random constraint satisfaction problems, SIAM Journal on Computing, 37, 895-922 (2007) · Zbl 1139.68028
[26] Prosser, P., An empirical study of phase transitions in binary constraint satisfaction problems, Artificial Intelligence, 81, 81-109 (1996) · Zbl 1523.68093
[27] Smith, B., Constructing an asymptotic phase transition in random binary constraint satisfaction problems, Theoretical Computer Science, 265, 265-283 (2001) · Zbl 0992.68191
[28] Smith, B.; Dyer, M., Locating the phase transition in binary constraint satisfaction problems, Artificial Intelligence, 81, 155-181 (1996) · Zbl 1508.68348
[29] Wang, C.; Liu, T.; Cui, P.; Xu, K., A note on treewidth in random graphs, (5th Annual International Conference on Combinatorial Optimization and Applications (COCOA) (2011), Springer), 491-499 · Zbl 1342.05145
[30] Xu, K.; Boussemart, F.; Hemery, F.; Lecoutre, C., Random constraint satisfaction: Easy generation of hard (satisfiable) instances, Artificial Intelligence, 171, 514-534 (2007) · Zbl 1168.68554
[31] Xu, K.; Li, W., Exact phase transitions in random constraint satisfaction problems, Journal of Artificial Intelligence Research, 12, 93-103 (2000) · Zbl 0940.68099
[32] Xu, K.; Li, W., Many hard examples in exact phase transitions, Theoretical Computer Science, 355, 291-302 (2006) · Zbl 1088.68163
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.