{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T02:56:40Z","timestamp":1761620200825,"version":"build-2065373602"},"reference-count":96,"publisher":"Elsevier","isbn-type":[{"type":"print","value":"9780444527264"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1016\/s1574-6526(06)80022-2","type":"book-chapter","created":{"date-parts":[[2008,2,26]],"date-time":"2008-02-26T16:51:39Z","timestamp":1204044699000},"page":"639-664","source":"Crossref","is-referenced-by-count":9,"title":["Randomness and Structure"],"prefix":"10.1016","member":"78","reference":[{"key":"10.1016\/S1574-6526(06)80022-2_bib1","series-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'01)","first-page":"719","article-title":"The phase transition in 1-in-k SAT and NAE SAT","author":"Achlioptas","year":"2001"},{"key":"10.1016\/S1574-6526(06)80022-2_bib2","series-title":"Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-00)","article-title":"Generating Satisfiable Instances","author":"Achlioptas","year":"2000"},{"issue":"1\u20132","key":"10.1016\/S1574-6526(06)80022-2_bib3","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0304-3975(01)00154-2","article-title":"Rigorous results for (2+p)-SAT","volume":"265","author":"Achlioptas","year":"2001","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S1574-6526(06)80022-2_bib4","series-title":"Proceedings of Third International Conference on Principles and Practice of Constraint Programming (CP97)","first-page":"107","article-title":"Random constraint satisfaction: A more accurate picture","author":"Achlioptas","year":"1997"},{"issue":"4","key":"10.1016\/S1574-6526(06)80022-2_bib5","first-page":"947","article-title":"The threshold for random k-SAT is 2k log(2) \u2013 o(k)","volume":"17","author":"Achlioptas","year":"2004","journal-title":"Journal of the AMS"},{"key":"10.1016\/S1574-6526(06)80022-2_bib6","series-title":"Proceedings of AAAI 2004","article-title":"Hiding satisfying assignments: Two are better than one","author":"Achlioptas","year":"2004"},{"key":"10.1016\/S1574-6526(06)80022-2_bib7","series-title":"Contributed to the DIMACS 1993 Challenge archive","article-title":"Random generation of test instances with controlled attributes","author":"Asahiro","year":"1993"},{"key":"10.1016\/S1574-6526(06)80022-2_bib8","series-title":"Proceedings of the 17th IJCAI","first-page":"183","article-title":"Phase transitions of PP-complete satisfiability problems","author":"Bailey","year":"2001"},{"key":"10.1016\/S1574-6526(06)80022-2_bib9","article-title":"The complexity of problems without backbones","author":"Beacham","year":"2000","journal-title":"Master's thesis, Department of Computing Science, University of Alberta"},{"year":"1985","series-title":"Random Graphs","author":"Bollob\u00e1s","key":"10.1016\/S1574-6526(06)80022-2_bib10"},{"key":"10.1016\/S1574-6526(06)80022-2_bib11","series-title":"Proceedings of 10th International Conference on Principles and Practice of Constraint Programming (CP2004)","article-title":"Statistical Regimes Across Constrainedness Regions","author":"Gomes","year":"2004"},{"key":"10.1016\/S1574-6526(06)80022-2_bib12","series-title":"Proceedings of the 12th IJCAI","first-page":"331","article-title":"Where the really hard problems are","author":"Cheeseman","year":"1991"},{"key":"10.1016\/S1574-6526(06)80022-2_bib13","series-title":"Proceedings of 7th International Conference on Principles and Practice of Constraint Programming (CP2001)","first-page":"408","article-title":"Formal Models of Heavy-tailed Behavior in Combinatorial Search","author":"Chen","year":"2001"},{"key":"10.1016\/S1574-6526(06)80022-2_bib14","series-title":"Proceedings of the 33rd Annual Symposium on Foundations of Computer Science","first-page":"620","article-title":"Mick gets some (the odds are on his side)","author":"Chvatal","year":"1992"},{"issue":"8","key":"10.1016\/S1574-6526(06)80022-2_bib15","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1103\/PhysRevLett.86.1654","article-title":"Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-satisfiability problem","volume":"86","author":"Cocco","year":"2001","journal-title":"Physical Review Letters"},{"key":"10.1016\/S1574-6526(06)80022-2_bib16","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(84)90075-1","article-title":"The complexity of completing partial Latin squares","volume":"8","author":"Colbourn","year":"1984","journal-title":"Discrete Applied Mathematics"},{"article-title":"Approximating the satisfiability threshold for random k-XOR-formulas","year":"2001","author":"Creognou","key":"10.1016\/S1574-6526(06)80022-2_bib17"},{"issue":"3","key":"10.1016\/S1574-6526(06)80022-2_bib18","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","article-title":"Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition","volume":"41","author":"Dechter","year":"1990","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80022-2_bib19","series-title":"Proceedings of Sixth International Conference on Theory and Applications of Satisfiability Testing (SAT-03)","article-title":"Kcnfs: An efficient solver for random k-SAT formulae","author":"Dequen","year":"2003"},{"key":"10.1016\/S1574-6526(06)80022-2_bib20","series-title":"Proceedings of the 18th IJCAI, International Joint Conference on Artificial Intelligence","article-title":"A backbone search heuristic for efficient solving of hard 3-SAT formulae","author":"Dubois","year":"2003"},{"issue":"12","key":"10.1016\/S1574-6526(06)80022-2_bib21","doi-asserted-by":"crossref","first-page":"127209","DOI":"10.1103\/PhysRevLett.87.127209","article-title":"Exact solutions for diluted spin glasses and optimization problems","volume":"87","author":"Franz","year":"2001","journal-title":"Phys. Rev. Letters"},{"issue":"4","key":"10.1016\/S1574-6526(06)80022-2_bib22","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","article-title":"Sharp thresholds of graph properties and the k-SAT problem","volume":"12","author":"Friedgut","year":"1999","journal-title":"Journal of the American Mathematical Society"},{"key":"10.1016\/S1574-6526(06)80022-2_bib23","series-title":"Proceedings of the 14th National Conference on AI","first-page":"327","article-title":"Summarizing CSP Hardness with Continuous Probability Distributions","author":"Frost","year":"1997"},{"key":"10.1016\/S1574-6526(06)80022-2_bib24","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1088\/0305-4470\/19\/9\/033","article-title":"Application of statistical mechanics to NP-complete problems in combinatorial optimisation","volume":"19","author":"Fu","year":"1986","journal-title":"J. Phys. A"},{"key":"10.1016\/S1574-6526(06)80022-2_bib25","series-title":"Proceedings of 10th International Conference on Principles and Practice of Constraint Programming (CP2004)","article-title":"Consistency and random constraint satisfaction problems","author":"Gao","year":"2004"},{"article-title":"Performance measurement and analysis of certain search algorithms","year":"1979","author":"Gaschnig","key":"10.1016\/S1574-6526(06)80022-2_bib26"},{"issue":"4","key":"10.1016\/S1574-6526(06)80022-2_bib27","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1023\/A:1011454308633","article-title":"Random constraint satisfaction: Flaws and structure","volume":"6","author":"Gent","year":"2001","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80022-2_bib28","series-title":"Proceedings of the 16th National Conference on AI","article-title":"Morphing: Combining structure and randomness","author":"Gent","year":"1999"},{"key":"10.1016\/S1574-6526(06)80022-2_bib29","series-title":"3rd International Conference on Principles and Practices of Constraint Programming (CP-97)","first-page":"327","article-title":"The constrainedness of arc consistency","author":"Gent","year":"1997"},{"key":"10.1016\/S1574-6526(06)80022-2_bib30","series-title":"Proceedings of the 13th National Conference on AI","first-page":"246","article-title":"The constrainedness of search","author":"Gent","year":"1996"},{"key":"10.1016\/S1574-6526(06)80022-2_bib31","series-title":"Proceedings of the 14th National Conference on AI","first-page":"315","article-title":"The scaling of search cost","author":"Gent","year":"1997"},{"key":"10.1016\/S1574-6526(06)80022-2_bib32","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0004-3702(94)90109-0","article-title":"Easy Problems are Sometimes Hard","volume":"70","author":"Gent","year":"1994","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80022-2_bib33","series-title":"Proceedings of the 8th International Symposium on Artificial Intelligence","first-page":"356","article-title":"Phase transitions from real computational problems","author":"Gent","year":"1995"},{"key":"10.1016\/S1574-6526(06)80022-2_bib34","series-title":"Proceedings of 12th ECAI","article-title":"Phase transitions and annealed theories: Number partitioning as a case study","author":"Gent","year":"1996"},{"key":"10.1016\/S1574-6526(06)80022-2_bib35","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/S0004-3702(96)00030-6","article-title":"The TSP phase transition","volume":"88","author":"Gent","year":"1996","journal-title":"Artificial Intelligence"},{"issue":"3","key":"10.1016\/S1574-6526(06)80022-2_bib36","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1111\/0824-7935.00069","article-title":"Analysis of heuristics for number partitioning","volume":"14","author":"Gent","year":"1998","journal-title":"Computational Intelligence"},{"key":"10.1016\/S1574-6526(06)80022-2_bib37","series-title":"Proceedings of the 16th National Conference on AI","article-title":"Beyond NP: the QSAT phase transition","author":"Gent","year":"1999"},{"key":"10.1016\/S1574-6526(06)80022-2_bib38","series-title":"Mathematical Foundations of Computer Science","first-page":"264","article-title":"A threshold for unsatisfiability","author":"Goerdt","year":"1992"},{"key":"10.1016\/S1574-6526(06)80022-2_bib39","series-title":"Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97)","first-page":"221","article-title":"Problem Structure in the Presence of Perturbations","author":"Gomes","year":"1997"},{"key":"10.1016\/S1574-6526(06)80022-2_bib40","series-title":"Proceedings of the Thirteenth Conference On Uncertainty in Artificial Intelligence (UAI-97)","article-title":"Algorithm Portfolio Design: Theory vs. Practice","author":"Gomes","year":"1997"},{"key":"10.1016\/S1574-6526(06)80022-2_bib41","series-title":"Proceedings of Third International Conference on Principles and Practice of Constraint Programming (CP97)","first-page":"121","article-title":"Heavy-tailed Distributions in Combinatorial Search","author":"Gomes","year":"1997"},{"key":"10.1016\/S1574-6526(06)80022-2_bib42","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0004-3702(00)00081-3","article-title":"Algorithm portfolios","volume":"126","author":"Gomes","year":"2001","journal-title":"Artificial Intelligence"},{"issue":"1\/2","key":"10.1016\/S1574-6526(06)80022-2_bib43","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1023\/A:1006314320276","article-title":"Heavy-tailed phenomena in satisfiability and constraint satisfaction problems","volume":"24","author":"Gomes","year":"2000","journal-title":"Journal of Automated Reasoning"},{"key":"10.1016\/S1574-6526(06)80022-2_bib44","series-title":"Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98)","article-title":"Boosting Combinatorial Search Through Randomization","author":"Gomes","year":"1998"},{"key":"10.1016\/S1574-6526(06)80022-2_bib45","series-title":"The Fourth International Conference on Artificial Intelligence Planning Systems (AIPS'98)","article-title":"Randomization in backtrack search: Exploiting heavy-tailed profiles for solving hard scheduling problems","author":"Gomes","year":"1998"},{"key":"10.1016\/S1574-6526(06)80022-2_bib46","series-title":"Proceedings of the CP-95 workshop on Really Hard Problems","article-title":"Where the Exceptionally Hard Problems Are","author":"Grant","year":"1995"},{"key":"10.1016\/S1574-6526(06)80022-2_bib47","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0004-3702(94)90088-4","article-title":"The Hardest Constraint Problems: a Double Phase Transition","volume":"69","author":"Hogg","year":"1994","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80022-2_bib48","series-title":"Proceedings of 17th Annual Conference on Uncertainty in Artificial Intelli gence (UAI-01)","first-page":"235","article-title":"A bayesian approach to tackling hard computational problems","author":"Horvitz","year":"2001"},{"key":"10.1016\/S1574-6526(06)80022-2_bib49","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0004-3702(87)90033-6","article-title":"Phase Transitions in Artificial Intelligence Systems","volume":"33","author":"Huberman","year":"1987","journal-title":"Artificial Intelligence"},{"issue":"265","key":"10.1016\/S1574-6526(06)80022-2_bib50","first-page":"51","article-title":"An economics approach to hard computational problems","author":"Huberman","year":"1993","journal-title":"Science"},{"key":"10.1016\/S1574-6526(06)80022-2_bib51","series-title":"Proc. of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05)","article-title":"Optimal Refutations for Constraint Satisfaction Problems","author":"Hulubei","year":"2005"},{"issue":"2","key":"10.1016\/S1574-6526(06)80022-2_bib52","article-title":"The impact of search heuristics on heavy-tailed behaviour","volume":"11","author":"Hulubei","year":"2006","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80022-2_bib53","series-title":"Proceedings of 6th International Conference on Theory and Applications of Satisfiability Testing","article-title":"Backdoor sets for random 3-SAT","author":"Interian","year":"2003"},{"key":"10.1016\/S1574-6526(06)80022-2_bib54","series-title":"Proceedings of the Second International Workshop on Constraint Propagation and Implementation, CP 2005","article-title":"Structure and problem hardness: Asymmetry and DPLL proofs in SAT-based planning","author":"Hoffmann","year":"2005"},{"key":"10.1016\/S1574-6526(06)80022-2_bib55","series-title":"Proceedings of 10th International Conference on Principles and Practice of Constraint Programming (CP2004)","article-title":"How much backtracking does it take to color random graphs? Rigorous results on heavy tails","author":"Jia","year":"2004"},{"key":"10.1016\/S1574-6526(06)80022-2_bib56","series-title":"Proceedings of AAAI 2005","article-title":"Generating hard satisfiable formulas by hiding solutions deceptively","author":"Jia","year":"2005"},{"key":"10.1016\/S1574-6526(06)80022-2_bib57","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/rsa.3240070105","article-title":"Tail bounds for occupancy and the satisfiability threshold conjecture","volume":"7","author":"Kamath","year":"1995","journal-title":"Randomized Structure and Algorithms"},{"key":"10.1016\/S1574-6526(06)80022-2_bib58","series-title":"Proceedings of the 18th National Conference on AI","first-page":"674","article-title":"Dynamic restart policies","author":"Kautz","year":"2002"},{"key":"10.1016\/S1574-6526(06)80022-2_bib59","series-title":"Proceedings of the 20th National Conference on AI","article-title":"Backbones and backdoors in satisfiability","author":"Kilby","year":"2005"},{"key":"10.1016\/S1574-6526(06)80022-2_bib60","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","article-title":"Critical behaviour in the satisfiability of random Boolean expressions","volume":"264","author":"Kirkpatrick","year":"1994","journal-title":"Science"},{"key":"10.1016\/S1574-6526(06)80022-2_bib61","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/PL00009274","article-title":"Approximating Latin square extensions","volume":"24","author":"Kumar","year":"1999","journal-title":"Algorithmica"},{"key":"10.1016\/S1574-6526(06)80022-2_bib62","series-title":"Proceedings of the 15th IJCAI","first-page":"366","article-title":"Heuristics based on unit propagation for satisfiability problems","author":"Li","year":"1997"},{"key":"10.1016\/S1574-6526(06)80022-2_bib63","first-page":"173","article-title":"Optimal speedup of Las Vegas algorithms","volume":"47","author":"Luby","year":"1993"},{"key":"10.1016\/S1574-6526(06)80022-2_bib64","series-title":"Proceedings of LICS workshop on Theory and Applications of Satisfiability Testing (SAT 2001)","article-title":"Stochastic systematic search algorithms for satisfiability","author":"Lynce","year":"2001"},{"key":"10.1016\/S1574-6526(06)80022-2_bib65","series-title":"Fifth International Symposium on the Theory and Applications of Satisfiability Testing (SAT'02)","article-title":"Complete unrestricted backtracking algorithms for satisfiability","author":"Lynce","year":"2002"},{"key":"10.1016\/S1574-6526(06)80022-2_bib66","series-title":"Proceedings of 8th International Conference on Principles and Practice of Constraint Programming (CP2002)","article-title":"The resolution complexity of constraint satisfaction","author":"Mitchell","year":"2002"},{"key":"10.1016\/S1574-6526(06)80022-2_bib67","series-title":"Proceedings of the 10th National Conference on AI","first-page":"459","article-title":"Hard and Easy Distributions of SAT Problems","author":"Mitchell","year":"1992"},{"key":"10.1016\/S1574-6526(06)80022-2_bib68","series-title":"Proceedings of 44th Symposium on Foundations of Computer Science (FOCS 2003)","article-title":"The resolution complexity of random constraint satisfaction problems","author":"Molloy","year":"2003"},{"issue":"3\u20134","key":"10.1016\/S1574-6526(06)80022-2_bib69","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G","article-title":"2+p SAT: Relation of typical-case complexity to the nature of the phase transition","volume":"15","author":"Monasson","year":"1999","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/S1574-6526(06)80022-2_bib70","series-title":"Proceedings of Design Automation Conference","first-page":"530","article-title":"Chaff: Engineering an efficient SAT solver","author":"Moskewicz","year":"2001"},{"key":"10.1016\/S1574-6526(06)80022-2_bib71","series-title":"Proceedings of the 20th National Conference on AI","first-page":"436","article-title":"Generation of hard non-clausal random satisfiability problems","author":"Navarro","year":"2005"},{"key":"10.1016\/S1574-6526(06)80022-2_bib72","series-title":"Proceedings of SAT 2004","article-title":"Detecting backdoor sets with respect to horn and binary clauses","author":"Nishimura","year":"2004"},{"key":"10.1016\/S1574-6526(06)80022-2_bib73","series-title":"Proceedings of the 11th ECAI","first-page":"95","article-title":"Binary constraint satisfaction problems: Some are harder than others","author":"Prosser","year":"1994"},{"key":"10.1016\/S1574-6526(06)80022-2_bib74","series-title":"Proceedings of 12th National Conference on Artificial Intelligence","first-page":"337","article-title":"Noise strategies for improving local search","author":"Selman","year":"1994"},{"key":"10.1016\/S1574-6526(06)80022-2_bib75","series-title":"Proceedings of the ECAI-98 workshop on non-binary constraints","article-title":"Arc Consistency and Quasigroup Completion","author":"Shaw","year":"1998"},{"key":"10.1016\/S1574-6526(06)80022-2_bib76","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0898-1221(94)00219-B","article-title":"Automated reasoning and exhaustive search: quasigroup existence problems","volume":"29","author":"Slaney","year":"1995","journal-title":"Computers and Mathematics with Applications"},{"key":"10.1016\/S1574-6526(06)80022-2_bib77","series-title":"Proceedings of the 13th ECAI","first-page":"244","article-title":"On the hardness of decision and optimisation problems","author":"Slaney","year":"1998"},{"key":"10.1016\/S1574-6526(06)80022-2_bib78","series-title":"Proceedings of 17th IJCAI","article-title":"Backbones in optimization and approximation","author":"Slaney","year":"2001"},{"key":"10.1016\/S1574-6526(06)80022-2_bib79","series-title":"Proceedings of the 5th International Symposium on the Theory and Applications of Satisfiability Testing, SAT 2002","article-title":"Phase transition behavior: from decision to optimization","author":"Slaney","year":"2002"},{"key":"10.1016\/S1574-6526(06)80022-2_bib80","series-title":"Proceedings of the 11th ECAI","article-title":"The phase transition in constraint satisfaction problems: A closer look at the mushy region","author":"Smith","year":"1994"},{"key":"10.1016\/S1574-6526(06)80022-2_bib81","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/S0304-3975(01)00166-9","article-title":"Constructing an asymptotic phase transition in random binary constraint satisfaction","volume":"265","author":"Smith","year":"2000","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S1574-6526(06)80022-2_bib82","doi-asserted-by":"crossref","DOI":"10.1007\/s10817-005-9007-9","article-title":"Backdoor sets for DLL solvers","author":"Szeider","year":"2006","journal-title":"Journal of Automated Reasoning"},{"key":"10.1016\/S1574-6526(06)80022-2_bib83","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1613\/jair.512","article-title":"The Gn,m phase transition is not hard for the Hamiltonian Cycle problem","volume":"9","author":"Vandegriend","year":"1998","journal-title":"Journal of Artificial Intelligence Research"},{"key":"10.1016\/S1574-6526(06)80022-2_bib84","series-title":"Proceedings of the 15th National Conference on AI","article-title":"The constrainedness knife-edge","author":"Walsh","year":"1998"},{"key":"10.1016\/S1574-6526(06)80022-2_bib85","series-title":"Proceedings of 16th IJCAI","article-title":"Search in a small world","author":"Walsh","year":"1999"},{"key":"10.1016\/S1574-6526(06)80022-2_bib86","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0004-3702(94)90104-X","article-title":"Exploiting the deep structure of constraint problems","volume":"70","author":"Williams","year":"1994","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80022-2_bib87","series-title":"Proceedings of 18th IJCAI","article-title":"Backdoors to typical case complexity","author":"Williams","year":"2003"},{"key":"10.1016\/S1574-6526(06)80022-2_bib88","series-title":"Proceedings of Sixth International Conference on Theory and Applications of Satisfiability Testing (SAT-03)","article-title":"On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search","author":"Williams","year":"2003"},{"key":"10.1016\/S1574-6526(06)80022-2_bib89","series-title":"Proceedings of the 19th International Conference on AI","article-title":"A simple model to generate hard satisfiable instances","author":"Xu","year":"2005"},{"key":"10.1016\/S1574-6526(06)80022-2_bib90","series-title":"Proceedings of IJCAI 2005","article-title":"A simple model to generate hard satisfiable instances","author":"Xu","year":"2005"},{"key":"10.1016\/S1574-6526(06)80022-2_bib91","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1613\/jair.696","article-title":"Exact phase transitions in random constraint satisfaction problems","volume":"12","author":"Xu","year":"2000","journal-title":"Journal of Artificial Intelligence Research"},{"key":"10.1016\/S1574-6526(06)80022-2_bib92","series-title":"Proceedings of the Twelfth International Conference on Inductive Logic Program","article-title":"Lattice-search runtime distributions may be heavy-tailed","author":"Zelezny","year":"2002"},{"key":"10.1016\/S1574-6526(06)80022-2_bib93","series-title":"Proceedings of International Symposium on AI and Math","article-title":"A random jump strategy for combinatorial search","author":"Zhang","year":"2002"},{"key":"10.1016\/S1574-6526(06)80022-2_bib94","series-title":"Proceedings of 7th International Conference on Principles and Practice of Constraint Programming (CP2001)","article-title":"Phase transitions and backbones of 3-SAT and Maximum 3-SAT","author":"Zhang","year":"2001"},{"key":"10.1016\/S1574-6526(06)80022-2_bib95","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1613\/jair.1389","article-title":"Phase transitions and backbones of the asymmetric traveling salesman problem","volume":"21","author":"Zhang","year":"2004","journal-title":"JAIR"},{"issue":"1\u20132","key":"10.1016\/S1574-6526(06)80022-2_bib96","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0004-3702(95)00054-2","article-title":"A study of complexity transitions on the asymmetric traveling salesman problem","volume":"81","author":"Zhang","year":"1996","journal-title":"Artificial Intelligence"}],"container-title":["Foundations of Artificial Intelligence","Handbook of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1574652606800222?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1574652606800222?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T02:54:07Z","timestamp":1761620047000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1574652606800222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9780444527264"],"references-count":96,"URL":"https:\/\/doi.org\/10.1016\/s1574-6526(06)80022-2","relation":{},"ISSN":["1574-6526"],"issn-type":[{"type":"print","value":"1574-6526"}],"subject":[],"published":{"date-parts":[[2006]]}}}