Random constraint satisfaction: easy generation of hard (satisfiable) instances. (English) Zbl 1168.68554
Summary: We show that the models of random CSP instances proposed by K. Xu and W. Li [J. Artif. Intell. Res. (JAIR) 12, 93–103 (2000; Zbl 0940.68099); Theor. Comput. Sci. 355, No. 3, 291–302 (2006; Zbl 1088.68163)] are of theoretical and practical interest. Indeed, these models, called RB and RD, present several nice features. First, it is quite easy to generate random instances of any arity since no particular structure has to be integrated, or property enforced, in such instances. Then, the existence of an asymptotic phase transition can be guaranteed while applying a limited restriction on domain size and on constraint tightness. In that case, a threshold point can be precisely located and all instances have the guarantee to be hard at the threshold, i.e., to have an exponential tree-resolution complexity. Next, a formal analysis shows that it is possible to generate forced satisfiable instances whose hardness is similar to unforced satisfiable ones. This analysis is supported by some representative results taken from an intensive experimentation that we have carried out, using complete and incomplete search methods.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | D. Achlioptas, C. Gomes, H. Kautz, B. Selman, Generating satisfiable problem instances, in: Proceedings of AAAI’00, 2000, pp. 256-301; D. Achlioptas, C. Gomes, H. Kautz, B. Selman, Generating satisfiable problem instances, in: Proceedings of AAAI’00, 2000, pp. 256-301 |
| [2] | D. Achlioptas, H. Jia, C. Moore, Hiding satisfying assignments: two are better than one, in: Proceedings of AAAI’04, 2004, pp. 131-136; D. Achlioptas, H. Jia, C. Moore, Hiding satisfying assignments: two are better than one, in: Proceedings of AAAI’04, 2004, pp. 131-136 · Zbl 1080.68653 |
| [3] | D. Achlioptas, L.M. Kirousis, E. Kranakis, D. Krizanc, M.S.O. Molloy, Y.C. Stamatiou, Random constraint satisfaction: a more accurate picture, in: Proceedings of CP’97, 1997, pp. 107-120; D. Achlioptas, L.M. Kirousis, E. Kranakis, D. Krizanc, M.S.O. Molloy, Y.C. Stamatiou, Random constraint satisfaction: a more accurate picture, in: Proceedings of CP’97, 1997, pp. 107-120 · Zbl 0984.68085 |
| [4] | D. Achlioptas, C. Moore, The asymptotic order of the random k-SAT threshold, in: Proceedings of FOCS’02, 2002, pp. 779-788; D. Achlioptas, C. Moore, The asymptotic order of the random k-SAT threshold, in: Proceedings of FOCS’02, 2002, pp. 779-788 |
| [5] | Barthel, W.; Hartmann, A. K.; Leone, M.; Ricci-Tersenghi, F.; Weigt, M.; Zecchina, R., Hiding solutions in random satisfiability problems: a statistical mechanics approach, Physical Review Letters, 88, 18 (2002) |
| [6] | Ben-Sasson, E.; Wigderson, A., Short proofs are narrow—resolution made simple, Journal of the ACM, 48, 2, 149-169 (2001) · Zbl 1089.03507 |
| [7] | C. Bessiere, J. Régin, Arc consistency for general constraint networks: preliminary results, in: Proceedings of IJCAI’97, 1997, pp. 398-404; C. Bessiere, J. Régin, Arc consistency for general constraint networks: preliminary results, in: Proceedings of IJCAI’97, 1997, pp. 398-404 |
| [8] | Bessiere, C.; Régin, J. C.; Yap, R. H.C.; Zhang, Y., An optimal coarse-grained arc consistency algorithm, Artificial Intelligence, 165, 2, 165-185 (2005) · Zbl 1132.68691 |
| [9] | F. Boussemart, F. Hemery, C. Lecoutre, L. Sais, Boosting systematic search by weighting constraints, in: Proceedings of ECAI’04, 2004, pp. 146-150; F. Boussemart, F. Hemery, C. Lecoutre, L. Sais, Boosting systematic search by weighting constraints, in: Proceedings of ECAI’04, 2004, pp. 146-150 |
| [10] | P. Cheeseman, B. Kanefsky, W.M. Taylor, Where the really hard problems are, in: Proceedings of IJCAI’91, 1991, pp. 331-337; P. Cheeseman, B. Kanefsky, W.M. Taylor, Where the really hard problems are, in: Proceedings of IJCAI’91, 1991, pp. 331-337 · Zbl 0747.68064 |
| [11] | S.A. Cook, D.G. Mitchell, Finding Hard Instances of the Satisfiability Problem: A Survey, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 35, 1997; S.A. Cook, D.G. Mitchell, Finding Hard Instances of the Satisfiability Problem: A Survey, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 35, 1997 · Zbl 0889.68073 |
| [12] | Debruyne, R.; Bessiere, C., Domain filtering consistencies, Journal of Artificial Intelligence Research, 14, 205-230 (2001) · Zbl 0970.68125 |
| [13] | O. Dubois, Y. Boufkhad, J. Mandler, Typical random 3-sat formulae and the satisfiability threshold, in: Proceedings of SODA’00, 2000, pp. 126-127; O. Dubois, Y. Boufkhad, J. Mandler, Typical random 3-sat formulae and the satisfiability threshold, in: Proceedings of SODA’00, 2000, pp. 126-127 · Zbl 0959.68135 |
| [14] | A.M. Frieze, M. Molloy, The satisfiability threshold for randomly generated binary constraint satisfaction problems, in: Proceedings of Random’03, 2003, pp. 275-289; A.M. Frieze, M. Molloy, The satisfiability threshold for randomly generated binary constraint satisfaction problems, in: Proceedings of Random’03, 2003, pp. 275-289 · Zbl 1279.68302 |
| [15] | Y. Gao, J. Culberson, Consistency and random constraint satisfaction models with a high constraint tightness, in: Proceedings of CP’04, 2004, pp. 17-31; Y. Gao, J. Culberson, Consistency and random constraint satisfaction models with a high constraint tightness, in: Proceedings of CP’04, 2004, pp. 17-31 · Zbl 1152.68552 |
| [16] | Gent, I. P.; MacIntyre, E.; Prosser, P.; Smith, B. M.; Walsh, T., Random constraint satisfaction: flaws and structure, Journal of Constraints, 6, 4, 345-372 (2001) · Zbl 0992.68193 |
| [17] | I.P. Gent, E. MacIntyre, P. Prosser, T. Walsh, The constrainedness of search, in: Proceedings of AAAI-96, 1996, pp. 246-252; I.P. Gent, E. MacIntyre, P. Prosser, T. Walsh, The constrainedness of search, in: Proceedings of AAAI-96, 1996, pp. 246-252 |
| [18] | C.P. Gomes, C. Fernández, B. Selman, C. Bessiere, Statistical regimes across constrainedness regions, in: Proceedings of CP’04, 2004, pp. 32-46; C.P. Gomes, C. Fernández, B. Selman, C. Bessiere, Statistical regimes across constrainedness regions, in: Proceedings of CP’04, 2004, pp. 32-46 · Zbl 1152.68555 |
| [19] | Haralick, R. M.; Elliott, G. L., Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence, 14, 263-313 (1980) |
| [20] | R. Impagliazzo, L. Levin, M. Luby, Pseudo-random number generation from one-way functions, in: Proceedings of STOC’89, 1989, pp. 12-24; R. Impagliazzo, L. Levin, M. Luby, Pseudo-random number generation from one-way functions, in: Proceedings of STOC’89, 1989, pp. 12-24 |
| [21] | H. Jia, C. Moore, B. Selman, From spin glasses to hard satisfiable formulas, in: Proceedings of SAT’04, 2004; H. Jia, C. Moore, B. Selman, From spin glasses to hard satisfiable formulas, in: Proceedings of SAT’04, 2004 · Zbl 1122.68605 |
| [22] | A.C. Kaporis, L.M. Kirousis, E.G. Lalas, The probabilistic analysis of a greedy satisfiability algorithm, in: Proceedings of ESA’02, 2002, pp. 574-585; A.C. Kaporis, L.M. Kirousis, E.G. Lalas, The probabilistic analysis of a greedy satisfiability algorithm, in: Proceedings of ESA’02, 2002, pp. 574-585 · Zbl 1019.68814 |
| [23] | C. Lecoutre, F. Boussemart, F. Hemery, Exploiting multidirectionality in coarse-grained arc consistency algorithms, in: Proceedings of CP’03, 2003, pp. 480-494; C. Lecoutre, F. Boussemart, F. Hemery, Exploiting multidirectionality in coarse-grained arc consistency algorithms, in: Proceedings of CP’03, 2003, pp. 480-494 |
| [24] | C. Lecoutre, F. Boussemart, F. Hemery, Implicit random CSPs, in: Proceedings of ICTAI’03, 2003, pp. 482-486; C. Lecoutre, F. Boussemart, F. Hemery, Implicit random CSPs, in: Proceedings of ICTAI’03, 2003, pp. 482-486 |
| [25] | C. Lecoutre, F. Boussemart, F. Hemery, Backjump-based techniques versus conflict-directed heuristics, in: Proceedings of ICTAI’04, 2004, pp. 549-557; C. Lecoutre, F. Boussemart, F. Hemery, Backjump-based techniques versus conflict-directed heuristics, in: Proceedings of ICTAI’04, 2004, pp. 549-557 |
| [26] | C. Lecoutre, R. Szymanek, Generalized arc consistency for positive table constraints, in: Proceedings of CP’06, 2006, pp. 284-298; C. Lecoutre, R. Szymanek, Generalized arc consistency for positive table constraints, in: Proceedings of CP’06, 2006, pp. 284-298 · Zbl 1335.90096 |
| [27] | Mackworth, A. K., Consistency in networks of relations, Artificial Intelligence, 8, 1, 99-118 (1977) · Zbl 0341.68061 |
| [28] | Mazure, B.; Sais, L.; Gregoire, E., Boosting complete techniques thanks to local search methods, Annals of Mathematics and Artificial Intelligence, 22, 319-331 (1998) · Zbl 0905.68143 |
| [29] | D.G. Mitchell, Some random CSPs are hard for resolution, 2000, submitted for publication; D.G. Mitchell, Some random CSPs are hard for resolution, 2000, submitted for publication |
| [30] | D.G. Mitchell, Resolution complexity of random constraints, in: Proceedings of CP’02, 2002, pp. 295-309; D.G. Mitchell, Resolution complexity of random constraints, in: Proceedings of CP’02, 2002, pp. 295-309 |
| [31] | Molloy, M., Models for random constraint satisfaction problems, SIAM Journal of Computing, 32, 4, 935-949 (2003) · Zbl 1029.68118 |
| [32] | P. Morris, The breakout method for escaping from local minima, in: Proceedings of AAAI’93, 1993, pp. 40-45; P. Morris, The breakout method for escaping from local minima, in: Proceedings of AAAI’93, 1993, pp. 40-45 |
| [33] | Secure Hash Standard. National Institute of Standards and Technology (2002), FIPS 180-2 |
| [34] | Prosser, P., An empirical study of phase transitions in binary constraint satisfaction problems, Artificial Intelligence, 81, 81-109 (1996) · Zbl 1523.68093 |
| [35] | R. Rivest, The MD5 message-digest algorithm, MIT Laboratory for Computer Science and RSA Data Security, Inc., 1992. Request for Comments 1321; R. Rivest, The MD5 message-digest algorithm, MIT Laboratory for Computer Science and RSA Data Security, Inc., 1992. Request for Comments 1321 |
| [36] | D. Sabin, E. Freuder, Contradicting conventional wisdom in constraint satisfaction, in: Proceedings of CP’94, 1994, pp. 10-20; D. Sabin, E. Freuder, Contradicting conventional wisdom in constraint satisfaction, in: Proceedings of CP’94, 1994, pp. 10-20 |
| [37] | B. Selman, H. Kautz, Domain-independent extensions to GSAT: solving large structured satisfiability problems, in: Proceedings of IJCAI’93, 1993, pp. 290-295; B. Selman, H. Kautz, Domain-independent extensions to GSAT: solving large structured satisfiability problems, in: Proceedings of IJCAI’93, 1993, pp. 290-295 |
| [38] | Smith, B. M., Constructing an asymptotic phase transition in random binary constraint satisfaction problems, Theoretical Computer Science, 265, 265-283 (2001) · Zbl 0992.68191 |
| [39] | Smith, B. M.; Dyer, M. E., Locating the phase transition in binary constraint satisfaction problems, Artificial Intelligence, 81, 155-181 (1996) · Zbl 1508.68348 |
| [40] | J.R. Thornton, Constraint weighting local search for constraint satisfaction, PhD thesis, Griffith University, Australia, 2000; J.R. Thornton, Constraint weighting local search for constraint satisfaction, PhD thesis, Griffith University, Australia, 2000 |
| [41] | Williams, C.; Hogg, T., Exploiting the deep structure of constraint problems, Artificial Intelligence, 70, 73-117 (1994) · Zbl 0938.68827 |
| [42] | K. Xu, A study on the phase transitions of SAT and CSP (in Chinese), PhD thesis, Beihang University, 2000; K. Xu, A study on the phase transitions of SAT and CSP (in Chinese), PhD thesis, Beihang University, 2000 |
| [43] | K. Xu, F. Boussemart, F. Hemery, C. Lecoutre, A simple model to generate hard satisfiable instances, in: Proceedings of IJCAI’05, 2005, pp. 337-342; K. Xu, F. Boussemart, F. Hemery, C. Lecoutre, A simple model to generate hard satisfiable instances, in: Proceedings of IJCAI’05, 2005, pp. 337-342 |
| [44] | Xu, K.; Li, W., Exact phase transitions in random constraint satisfaction problems, Journal of Artificial Intelligence Research, 12, 93-103 (2000) · Zbl 0940.68099 |
| [45] | Xu, K.; Li, W., Many hard examples in exact phase transitions with application to generating hard satisfiable instances, Theoretical Computer Science, 355, 291-302 (2006), Technical report, CoRR Report cs.CC/0302001, Revised version in · 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.
