{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:11Z","timestamp":1759637951567},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2005,8,1]],"date-time":"2005-08-01T00:00:00Z","timestamp":1122854400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2005,8]]},"DOI":"10.1007\/s10472-005-7033-2","type":"journal-article","created":{"date-parts":[[2005,9,15]],"date-time":"2005-09-15T07:41:11Z","timestamp":1126770071000},"page":"353-372","source":"Crossref","is-referenced-by-count":9,"title":["Spines of random constraint satisfaction problems: definition and connection with computational complexity"],"prefix":"10.1007","volume":"44","author":[{"given":"Gabriel","family":"Istrate","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Boettcher","sequence":"additional","affiliation":[]},{"given":"Allon G.","family":"Percus","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17033_CR1","unstructured":"D. Achlioptas, A. Chtcherba, G. Istrate and C. Moore, The phase transition in random 1-in-k SAT and NAE 3SAT, in: Proc. of the 13th ACM-SIAM Symposium on Discrete Algorithms (2001). Journal version in preparation."},{"issue":"1","key":"17033_CR2","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7","volume":"14","author":"D. Achlioptas","year":"1999","unstructured":"D. Achlioptas and E. Friedgut, A sharp threshold for k-colorability, Random Structures and Algorithms 14(1) (1999) 63\u201370.","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"17033_CR3","doi-asserted-by":"crossref","first-page":"1048","DOI":"10.1137\/S0097539700369156","volume":"31","author":"P. Beame","year":"2002","unstructured":"P. Beame, R. Karp, T. Pitassi and M. Saks, The efficiency of resolution and Davis\u2013Putnam procedures, SIAM Journal of Computing 31(4) (2002) 1048\u20131075.","journal-title":"SIAM Journal of Computing"},{"key":"17033_CR4","unstructured":"P. Beame and T. Pitassi, Propositional proof complexity: Past present and future, in: Current Trends in Theoretical Computer Science (2001) pp. 42\u201370."},{"key":"17033_CR5","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson and A. Wigderson, Short proofs are narrow: Resolution made simple, Journal of the ACM 48(2) (2001).","DOI":"10.1145\/375827.375835"},{"key":"17033_CR6","doi-asserted-by":"crossref","first-page":"5201","DOI":"10.1088\/0305-4470\/32\/28\/302","volume":"32","author":"S. Boettcher","year":"1999","unstructured":"S. Boettcher, A extremal optimization of graph partition at the percolation threshold, J. Phys. Math. Gen. 32 (1999) 5201\u20135211.","journal-title":"J. Phys. Math. Gen."},{"key":"17033_CR7","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0004-3702(00)00007-2","volume":"119","author":"S. Boettcher","year":"2000","unstructured":"S. Boettcher and A. Percus, Nature\u2019s way of optimizing, Artificial Intelligence 119 (2000) 275\u2013286.","journal-title":"Artificial Intelligence"},{"key":"17033_CR8","doi-asserted-by":"crossref","first-page":"066703","DOI":"10.1103\/PhysRevE.69.066703","volume":"69","author":"S. Boettcher","year":"2004","unstructured":"S. Boettcher and A.G. Percus, Extremal optimization at the phase transition of the 3-coloring problem, Physical Review E 69 (2004) 066703.","journal-title":"Physical Review E"},{"key":"17033_CR9","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s, Random Graphs (Academic Press, New York, 1985)."},{"key":"17033_CR10","unstructured":"B. Bollob\u00e1s, C. Borgs, J.T. Chayes, J.H. Kim and D.B. Wilson, The scaling window of the 2-SAT transition, Technical Report, Los Alamos e-print server, http:\/\/xxx.lanl.gov\/ps\/math.CO\/9909031, 1999."},{"issue":"4","key":"17033_CR11","doi-asserted-by":"crossref","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) (1988) 759\u2013768.","journal-title":"Journal of the ACM"},{"issue":"2","key":"17033_CR12","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.ic.2004.01.002","volume":"190","author":"N. Creignou","year":"2004","unstructured":"N. Creignou and H. Daud\u00e9, Combinatorial sharpness criterion and phase transition classification for random CSPs, Information and Computation 190(2) (2004) 220\u2013238.","journal-title":"Information and Computation"},{"issue":"1\/2","key":"17033_CR13","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/S0304-3975(01)00164-5","volume":"265","author":"J. Culberson","year":"2001","unstructured":"J. Culberson and I. Gent, Frozen development in graph coloring, Theoretical Computer Science 265(1\/2) (2001) 227\u2013264.","journal-title":"Theoretical Computer Science"},{"key":"17033_CR14","first-page":"1017","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"E. Friedgut, Necessary and sufficient conditions for sharp thresholds of graph properties, and the k-SAT problem with an appendix by J. Bourgain, Journal of the AMS 12 (1999) 1017\u20131054.","journal-title":"Journal of the AMS"},{"key":"17033_CR15","series-title":"Springer Graduate Texts in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"N. Immerman, Descriptive Complexity, Springer Graduate Texts in Computer Science (Springer, Berlin, 1999)."},{"key":"17033_CR16","unstructured":"G. Istrate, Phase transitions and all that, Preprint CS.CC\/0211012, ACM Computer Repository at arXiv.org."},{"key":"17033_CR17","unstructured":"G. Istrate, Threshold properties of random constraint satisfaction problems, accepted to a special volume of Discrete Applied Mathematics on typical-case complexity and phase transitions."},{"key":"17033_CR18","unstructured":"G. Istrate, Descriptive complexity and first-order phase transitions (in progress)."},{"issue":"1\u20133","key":"17033_CR19","doi-asserted-by":"crossref","first-page":"123","DOI":"10.4064\/fm170-1-8","volume":"170","author":"J. Krajicek","year":"2001","unstructured":"J. Krajicek, On the weak pigeonhole principle, Fundamenta Matematicae 170(1\u20133) (2001) 123\u2013140.","journal-title":"Fundamenta Matematicae"},{"issue":"1\/2","key":"17033_CR20","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0304-3975(01)00149-9","volume":"265","author":"O. Martin","year":"2001","unstructured":"O. Martin, R. Monasson and R. Zecchina, Statistical mechanics methods and phase transitions in combinatorial optimization problems, Theoretical Computer Science 265(1\/2) (2001) 3\u201367.","journal-title":"Theoretical Computer Science"},{"key":"17033_CR21","doi-asserted-by":"crossref","unstructured":"D. Mitchell, Resolution complexity of random constraints, in: Eigth International Conference on Principles and Practice of Constraint Programming (2002).","DOI":"10.1007\/3-540-46135-3_20"},{"key":"17033_CR22","doi-asserted-by":"crossref","unstructured":"M. Molloy, Models for random constraint satisfaction problems, in: Proc. of the 32nd ACM Symposium on Theory of Computing (2002).","DOI":"10.1145\/509907.509941"},{"key":"17033_CR23","doi-asserted-by":"crossref","unstructured":"M. Molloy and M. Salavatipour, The resolution complexity of random constraint satisfaction problems, in: Proc. of the 44th Annual IEEE Symposium on Foundations of Computer Science (2003).","DOI":"10.1109\/SFCS.2003.1238207"},{"key":"17033_CR24","doi-asserted-by":"crossref","first-page":"1357","DOI":"10.1103\/PhysRevE.56.1357","volume":"56","author":"R. Monasson","year":"1997","unstructured":"R. Monasson and R. Zecchina, Statistical mechanics of the random k-SAT model, Physical Review E 56 (1997) 1357.","journal-title":"Physical Review E"},{"issue":"8","key":"17033_CR25","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R. Monasson","year":"1999","unstructured":"R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman and L. Troyansky, Determining computational complexity from characteristic phase transitions, Nature 400(8) (1999) 133\u2013137.","journal-title":"Nature"},{"issue":"3\/4","key":"17033_CR26","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","volume":"15","author":"R. Monasson","year":"1999","unstructured":"R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman and L. Troyansky, 2+p-SAT: Relation of typical-case complexity to the nature of the phase transition, Random Structures and Algorithms 15(3\/4) (1999) 414\u2013435.","journal-title":"Random Structures and Algorithms"},{"key":"17033_CR27","unstructured":"M.A. Trick, color.c graph coloring code, available at http:\/\/mat.gsia.cmu.edu\/COLOR\/solvers\/trick.c."},{"key":"17033_CR28","doi-asserted-by":"crossref","first-page":"268701","DOI":"10.1103\/PhysRevLett.89.268701","volume":"89","author":"R. Mulet","year":"2002","unstructured":"R. Mulet, A. Pagnani, M. Weigt and R. Zecchina, Coloring random graphs, Physical Review Letters 89 (2002) 268701.","journal-title":"Physical Review Letters"},{"key":"17033_CR29","doi-asserted-by":"crossref","first-page":"026702","DOI":"10.1103\/PhysRevE.63.026702","volume":"63","author":"F. Ricci-Tersenghi","year":"2001","unstructured":"F. Ricci-Tersenghi, M. Weigt and R. Zecchina, Simplest random k-satisfiability problem, Physical Review E 63 (2001) 026702.","journal-title":"Physical Review E"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-005-7033-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-005-7033-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-005-7033-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T17:51:48Z","timestamp":1559152308000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-005-7033-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,8]]}},"alternative-id":["17033"],"URL":"https:\/\/doi.org\/10.1007\/s10472-005-7033-2","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,8]]}}}