{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:03:31Z","timestamp":1725483811869},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441205"},{"type":"electronic","value":"9783540461357"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-46135-3_20","type":"book-chapter","created":{"date-parts":[[2007,5,15]],"date-time":"2007-05-15T05:59:47Z","timestamp":1179208787000},"page":"295-310","source":"Crossref","is-referenced-by-count":18,"title":["Resolution Complexity of Random Constraints"],"prefix":"10.1007","author":[{"given":"David G.","family":"Mitchell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,9,2]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, P. Beame, and M. Molloy. A sharp threshold in proof complexity. In Proc., 33rd Annual ACM Symp. on the Theory of Computing (STOC-01), pages 337\u2013346, 2001.","DOI":"10.1145\/380752.380820"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, L. Kirousis, E. Kranakis, D. Krizanc, M. Molloy, and Y. Stamatiou. Random constraint satisfaction: A more accurate picture. Constraints, 6(4):329\u2013344","DOI":"10.1023\/A:1011402324562"},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","volume":"43","author":"R. Aharoni","year":"1986","unstructured":"R. Aharoni and N. Linial. Minimal unsatisfiable formulas and minimal non-two-colorable hypergraphs. J. of Combinatorial Theory, Series A, 43:196\u2013204, 1986.","journal-title":"J. of Combinatorial Theory, Series A"},{"key":"20_CR4","unstructured":"Andrew B. Baker. Intelligent Backtracking on Constraint Satisfaction Problems: Experimental and Theoretical Results. PhD thesis, University of Oregon, 1995."},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"P. Beame, R. Karp, T. Pitassi, and M. Saks. On the complexity of unsatisfiability proofs for random k-CNF formulas. In Proc., 30th Annual ACM Symp. on the Theory of Computing (STOC-98), pages 561\u2013571, May 1998.","DOI":"10.1145\/276698.276870"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson and A. Wigderson. Short proofs are narrow: Resolution made simple. In Proc., 31st Annual Symp. on the Theory of Computing (STOC-99), pages 517\u2013526, May 1999. (Also appears as ECCC report TR99-022).","DOI":"10.1145\/301250.301392"},{"key":"20_CR7","unstructured":"P. Cheesman, B. Kanefsky, and W. M. Taylor. Where the really hard problems are. In Proc., 12th Int\u2019l. Joint Conf. on A. I. (IJCAI-91), 1991."},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"V. Chv\u00e1tal and B. Reed. Mick gets some (the odds are on his side). In Proc. of the 33rd Symp. on the Foundations of Comp. Sci. (FOCS-92), pages 620\u2013628, 1992.","DOI":"10.1109\/SFCS.1992.267789"},{"issue":"4","key":"20_CR9","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chv\u00e1tal","year":"1988","unstructured":"V. Chv\u00e1tal and E. Szemer\u00e9di. Many hard examples for resolution. Journal of the ACM, 35(4):759\u2013768, 1988.","journal-title":"Journal of the ACM"},{"key":"20_CR10","unstructured":"J. De Kleer. A comparison of ATMS and CSP techniques. In Proc. of the 11th Int\u2019l. Joint Conf. on A. I. (IJCAI-89), pages 290\u2013296, 1989."},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","volume":"41","author":"R. Dechter","year":"1990","unstructured":"R. Dechter. Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition. Artificial Intelligence, 41:273\u2013312, 1990.","journal-title":"Artificial Intelligence"},{"key":"20_CR12","volume-title":"Technical report","author":"R. Dechter","year":"1999","unstructured":"R. Dechter and D. Frost. Backtracking algorithms for constraint satisfaction problems. Technical report, Dept. of Inf. & Comp. Sci., U. of California, Irvine, 1999."},{"key":"20_CR13","unstructured":"J. Gashnig. Experimental case studies of backtrack vs. Waltz-type vs. new algorithms for satisficing assignment problems. In Proc. of the Canadian Artificial Intelligence Conference, pages 268\u2013277, 1978."},{"issue":"4","key":"20_CR14","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1023\/A:1011454308633","volume":"6","author":"I. P. Gent","year":"2001","unstructured":"I. P. Gent, E. MacIntyre, P. Prosser, B. M. Smith, and T. Walsh. Random constraint satisfaction: flaws and structure. Constraints, 6(4):345\u2013372, October 2001.","journal-title":"Constraints"},{"key":"20_CR15","unstructured":"O. Kullmann. Upper and lower bounds on the complexity of generalized resolution and generalized constraint satisfaction problems. Submitted, 2000."},{"key":"20_CR16","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0004-3702(85)90041-4","volume":"25","author":"A. K. Mackworth","year":"1985","unstructured":"A. K. Mackworth and E. C. Freuder. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence, 25:65\u201373, 1985.","journal-title":"Artificial Intelligence"},{"key":"20_CR17","unstructured":"D.G. Mitchell. Hard problems for CSP algorithms. In Proc., 15th Nat. Conf. on Artificial Intelligence (AAAI-98), pages 398\u2013405, 1998."},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"D. G. Mitchell. The Resolution Complexity of Constraint Satisfaction. PhD thesis, University of Toronto, 2002.","DOI":"10.1007\/3-540-46135-3_20"},{"key":"20_CR19","unstructured":"D.G. Mitchell. Constraint satisfaction and resolution. In preparation."},{"key":"20_CR20","unstructured":"D. G. Mitchell, B. Selman, and H. J. Levesque. Hard and easy distributions of SAT problems. In Proc. of the 10th Nat. Conf. on A. I. (AAAI\u201992), pages 459\u2013462, 1992."},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"M. Molloy. Models and thresholds for random constraint satisfaction problems. In Proc., 34th Annual Symp. on the Theory of Computing (STOC-02), pages 209\u2013217. ACM, 2002.","DOI":"10.1145\/509907.509941"},{"issue":"3","key":"20_CR22","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1111\/j.1467-8640.1993.tb00310.x","volume":"9","author":"P. Prosser","year":"1993","unstructured":"P. Prosser. Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence, 9(3):268\u2013299, August 1993.","journal-title":"Computational Intelligence"},{"key":"20_CR23","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0004-3702(95)00048-8","volume":"81","author":"P. Prosser","year":"1996","unstructured":"P. Prosser. An empirical study of phase transitions in binary constraint satisfaction problems. Artificial Intelligence, 81:81\u2013109, 1996.","journal-title":"Artificial Intelligence"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer. The complexity of satisfiability problems. In Proc., 10th Annual ACM Symp. on the Theory of Computing (STOC-78), pages 216\u2013226. ACM, 1978.","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming - CP 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46135-3_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,22]],"date-time":"2020-04-22T00:57:26Z","timestamp":1587517046000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46135-3_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441205","9783540461357"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-46135-3_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2002]]}}}