{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T10:45:31Z","timestamp":1761561931783},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,11,27]],"date-time":"2014-11-27T00:00:00Z","timestamp":1417046400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Sci. China Inf. Sci."],"published-print":{"date-parts":[[2015,3]]},"DOI":"10.1007\/s11432-014-5154-0","type":"journal-article","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T14:17:49Z","timestamp":1417529869000},"page":"1-11","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Experimental analyses on phase transitions in compiling satisfiability problems"],"prefix":"10.1007","volume":"58","author":[{"given":"Jian","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JiaNan","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MingHao","family":"Yin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,27]]},"reference":[{"key":"5154_CR1","first-page":"331","volume-title":"Proceedings of the 12th International Joint Conference on Artificial Intelligence, Sydney","author":"P Cheeseman","year":"1991","unstructured":"Cheeseman P, Kanefsky B, Taylor W M. Where the really hard problems are. In: Proceedings of the 12th International Joint Conference on Artificial Intelligence, Sydney, 1991. 331\u2013340"},{"key":"5154_CR2","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1613\/jair.696","volume":"12","author":"K Xu","year":"2000","unstructured":"Xu K, Li W. Exact phase transitions in random constraint satisfaction problems. J Artif Intell Res, 2000, 12: 93\u2013103","journal-title":"J Artif Intell Res"},{"key":"5154_CR3","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1038\/nature03602","volume":"435","author":"D Achlioptas","year":"2005","unstructured":"Achlioptas D, Naor A, Peres Y. Rigorous location of phase transitions in hard optimization problems. Nature, 2005, 435: 759\u2013764","journal-title":"Nature"},{"key":"5154_CR4","first-page":"648","volume-title":"Proceedings of the 16th National Conference on Artificial Intelligence and Eleventh Conference on Innovative Applications of Artificial Intelligence, Orlando","author":"I P Gent","year":"1999","unstructured":"Gent I P, Walsh T. Beyond NP: the QSAT phase transition. In: Proceedings of the 16th National Conference on Artificial Intelligence and Eleventh Conference on Innovative Applications of Artificial Intelligence, Orlando, 1999. 648\u2013653"},{"key":"5154_CR5","first-page":"34","volume-title":"Proceedings of 11th International Conference on Theory and Applications of Satisfiability Testing, Guangzhou","author":"N Creignou","year":"2008","unstructured":"Creignou N, Daud\u00e9 H, Egly U, et al. New results on the phase transition for random quantified boolean formulas. In: Proceedings of 11th International Conference on Theory and Applications of Satisfiability Testing, Guangzhou, 2008. 34\u201347"},{"key":"5154_CR6","first-page":"101","volume-title":"Proceedings of the 14th International Conference on Automated Planning and Scheduling, Whistler","author":"J Rintanen","year":"2004","unstructured":"Rintanen J. Phase transitions in classical planning: an experimental study. In: Proceedings of the 14th International Conference on Automated Planning and Scheduling, Whistler, 2004. 101\u2013110"},{"key":"5154_CR7","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/S0004-3702(96)00030-6","volume":"88","author":"I P Gent","year":"1996","unstructured":"Gent I P, Walsh T. The TSP phase transition. Artif Intell, 1996, 88: 349\u2013358","journal-title":"Artif Intell"},{"key":"5154_CR8","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1023\/A:1012328830929","volume":"33","author":"K Xu","year":"2001","unstructured":"Xu K, Li W. An average analysis of backtracking on random constraint satisfaction problems. Ann Math Artif Intell, 2001, 33: 21\u201337","journal-title":"Ann Math Artif Intell"},{"key":"5154_CR9","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.tcs.2006.01.001","volume":"355","author":"K Xu","year":"2006","unstructured":"Xu K, Li W. Many hard examples in exact phase transitions. Theor Comput Sci, 2006, 355: 291\u2013302","journal-title":"Theor Comput Sci"},{"key":"5154_CR10","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1613\/jair.3907","volume":"46","author":"S Cai","year":"2013","unstructured":"Cai S, Su K, Luo C, et al. NuMVC: an efficient local search algorithm for minimum vertex cover. J Artif Intell Res, 2013, 46: 687\u2013716","journal-title":"J Artif Intell Res"},{"key":"5154_CR11","first-page":"441","volume-title":"Proceedings of the 26th AAAI Conference on Artificial Intelligence, Toronto","author":"S Cai","year":"2012","unstructured":"Cai S, Su K, Sattar A. Two new local search strategies for minimum vertex cover. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence, Toronto, 2012, 441\u2013447"},{"key":"5154_CR12","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s11023-012-9270-6","volume":"23","author":"L Li","year":"2013","unstructured":"Li L, Liu T, Xu K. Variable-centered consistency in model RB. Mind Machine, 2013, 23: 95\u2013103","journal-title":"Mind Machine"},{"key":"5154_CR13","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1007\/978-3-642-38756-2_30","volume-title":"Proceedings of 3rd Joint International Conference on Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Dalian","author":"C Wang","year":"2013","unstructured":"Wang C, Liu T, Xu K. Large hypertree width for sparse random hypergraphs. In: Proceedings of 3rd Joint International Conference on Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Dalian, 2013. 294\u2013302"},{"key":"5154_CR14","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.artint.2007.04.001","volume":"171","author":"K Xu","year":"2007","unstructured":"Xu K, Boussemart F, Hemery F, et al. Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif Intell, 2007, 171: 514\u2013534","journal-title":"Artif Intell"},{"key":"5154_CR15","doi-asserted-by":"crossref","first-page":"914","DOI":"10.1016\/j.artint.2010.11.004","volume":"175","author":"Y Fan","year":"2011","unstructured":"Fan Y, Shen J. On the phase transitions of random k-constraint satisfaction problems. Artif Intell, 2011, 175: 914\u2013927","journal-title":"Artif Intell"},{"key":"5154_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2012.08.003","volume":"193","author":"Y Fan","year":"2012","unstructured":"Fan Y, Shen J, Xu K. A general model and thresholds for random constraint satisfaction problems. Artif Intell, 2012, 193: 1\u201317","journal-title":"Artif Intell"},{"key":"5154_CR17","first-page":"324","volume-title":"Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena","author":"T Walsh","year":"2009","unstructured":"Walsh T. Where are the really hard manipulation problems? The phase transition in manipulating the veto rule. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, 2009. 324\u2013329"},{"key":"5154_CR18","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1142\/S012905411000774X","volume":"21","author":"J Zhou","year":"2010","unstructured":"Zhou J, Huang P, Yin M, et al. Phase transitions of EXPSPACE-Complete problems. Int J Found Comput Sci, 2010, 21: 1073\u20131088","journal-title":"Int J Found Comput Sci"},{"key":"5154_CR19","first-page":"183","volume-title":"Proceedings of the 17th International Joint Conference on Artificial Intelligence, Seattle","author":"D D Bailey","year":"2001","unstructured":"Bailey D D, Dalmau V, Kolaitis P G. Phase transitions of PP-Complete satisfiability problems. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence, Seattle, 2001. 183\u2013192"},{"key":"5154_CR20","volume-title":"Exact phase transition of backtrack-free search with implications on the power of greedy algorithms","author":"L Li","year":"2008","unstructured":"Li L, Liu T, Xu K. Exact phase transition of backtrack-free search with implications on the power of greedy algorithms. arXiv, 2008. arXiv:0811.3055"},{"key":"5154_CR21","first-page":"137","volume":"10","author":"M Cadoli","year":"1998","unstructured":"Cadoli M, and Donini F. A survey on knowledge compilation. AI Communications, 1998, 10: 137\u2013150","journal-title":"AI Communications"},{"key":"5154_CR22","first-page":"149","volume-title":"Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad","author":"N Narodytska","year":"2007","unstructured":"Narodytska N, Walsh T. Constraint and variable ordering heuristics for compiling configuration problems. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, 2007. 149\u2013154"},{"key":"5154_CR23","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1145\/226643.226644","volume":"43","author":"B Selman","year":"1996","unstructured":"Selman B, Kautz H A. Knowledge compilation and theory approximation. J ACM, 1996, 43: 193\u2013224","journal-title":"J ACM"},{"key":"5154_CR24","first-page":"627","volume-title":"Proceedings of the 18th National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, Edmonton","author":"A Darwiche","year":"2002","unstructured":"Darwiche A. A compiler for deterministic, decomposable negation normal form. In: Proceedings of the 18th National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, Edmonton, 2002. 627\u2013634"},{"key":"5154_CR25","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0004-3702(01)00162-X","volume":"135","author":"J Amilhastre","year":"2002","unstructured":"Amilhastre J, Fargier H, Marquis P. Consistency restoration and explanations in dynamic CSPs Application to configuration. Artif Intell, 2002, 135: 199\u2013234","journal-title":"Artif Intell"},{"key":"5154_CR26","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1613\/jair.2605","volume":"33","author":"R Mateescu","year":"2008","unstructured":"Mateescu R, Dechter R, Marinescu R. AND\/OR multi-valued decision diagrams (AOMDDs) for graphical models. J Artif Intell Res, 2008, 33: 465\u2013519","journal-title":"J Artif Intell Res"},{"key":"5154_CR27","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.989","volume":"17","author":"A Darwiche","year":"2002","unstructured":"Darwiche A, Marquis P. A knowledge compilation map. J Artif Intell Res, 2002, 17: 229\u2013264","journal-title":"J Artif Intell Res"},{"key":"5154_CR28","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0004-3702(95)00053-4","volume":"81","author":"R Schrag","year":"1996","unstructured":"Schrag R, Crawford J M. Implicates and prime implicates in Random 3-SAT. Artif Intell, 1996, 81: 199\u2013222","journal-title":"Artif Intell"},{"key":"5154_CR29","first-page":"364","volume-title":"SAT","author":"J Gao","year":"2011","unstructured":"Gao J, Yin M, Xu K. Phase transitions in knowledge compilation: an experimental study. SAT 2011, 364\u2013366"},{"key":"5154_CR30","first-page":"459","volume-title":"Proceedings of the 10th National Conference on Artificial Intelligence. San Jose","author":"D G Mitchell","year":"1992","unstructured":"Mitchell D G, Selman B, Levesque H J. Hard and easy distributions of SAT problems. In: Proceedings of the 10th National Conference on Artificial Intelligence. San Jose, 1992. 459\u2013465"},{"key":"5154_CR31","first-page":"1790","volume-title":"Proceedings of the 25th AAAI Conference on Artificial Intelligence, San Francisco","author":"P Huang","year":"2011","unstructured":"Huang P, Yin M, Xu K. Exact phase transitions and approximate algorithm of #CSP. In: Proceedings of the 25th AAAI Conference on Artificial Intelligence, San Francisco, 2011. 1790\u20131791"},{"key":"5154_CR32","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1613\/jair.601","volume":"10","author":"E Birnbaum","year":"1999","unstructured":"Birnbaum E, Lozinskii E L. The good old Davis-Putnam procedure helps counting models. J Artif Intell Res, 1999, 10: 457\u2013477","journal-title":"J Artif Intell Res"},{"key":"5154_CR33","first-page":"157","volume-title":"Proceedings of the 17th National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, Austin","author":"J Roberto","year":"2000","unstructured":"Roberto J, Bayardo Jr, Pehoushek J D. Counting models using connected components. In: Proceedings of the 17th National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, Austin, 2000. 157\u2013162"},{"key":"5154_CR34","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0747-7171(08)80029-6","volume":"9","author":"A Kean","year":"1990","unstructured":"Kean A, Tsiknis G. An incremental method for generating prime implicants\/implicates. J Symbolic Comput, 1990, 9: 185\u2013206","journal-title":"J Symbolic Comput"},{"key":"5154_CR35","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1006\/jcss.2001.1775","volume":"63","author":"C Umans","year":"2001","unstructured":"Umans C. The minimum equivalent DNF problem and shortest implicants. J Comput Syst Sci, 2001, 63: 597\u2013611","journal-title":"J Comput Syst Sci"},{"key":"5154_CR36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(95)00184-0","volume":"215","author":"Y Boufkhad","year":"1999","unstructured":"Boufkhad Y, Dubois O. Length of prime implicants and number of solutions of random CNF formulae. Theor Comput Sci, 1999, 215: 1\u201330","journal-title":"Theor Comput Sci"},{"key":"5154_CR37","first-page":"521","volume":"26","author":"B Selman","year":"1993","unstructured":"Selman B, Kautz H, Cohen B. Local search strategies for satisfiability testing. Clique Color Satisf 2nd DIMACS Implement Challenge, 1993, 26: 521\u2013532","journal-title":"Clique Color Satisf 2nd DIMACS Implement Challenge"}],"container-title":["Science China Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-014-5154-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11432-014-5154-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-014-5154-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,18]],"date-time":"2019-08-18T02:01:31Z","timestamp":1566093691000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11432-014-5154-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,27]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["5154"],"URL":"https:\/\/doi.org\/10.1007\/s11432-014-5154-0","relation":{},"ISSN":["1674-733X","1869-1919"],"issn-type":[{"value":"1674-733X","type":"print"},{"value":"1869-1919","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,27]]}}}