{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,12]],"date-time":"2023-01-12T19:49:15Z","timestamp":1673552955010},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2012,8,17]],"date-time":"2012-08-17T00:00:00Z","timestamp":1345161600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sci. China Inf. Sci."],"published-print":{"date-parts":[[2013,9]]},"DOI":"10.1007\/s11432-012-4653-0","type":"journal-article","created":{"date-parts":[[2012,8,16]],"date-time":"2012-08-16T18:27:58Z","timestamp":1345141678000},"page":"1-13","source":"Crossref","is-referenced-by-count":3,"title":["Exponential bounds for the random walk algorithm on random planted 3-SAT"],"prefix":"10.1007","volume":"56","author":[{"given":"YuRen","family":"Zhou","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,8,17]]},"reference":[{"key":"4653_CR1","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/321033.321034","volume":"7","author":"M Davis","year":"1960","unstructured":"Davis M, Putnam H. A computer procedure for quantification theory. J ACM, 1960, 7: 202\u2013215","journal-title":"J ACM"},{"key":"4653_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1023\/A:1006351428454","volume":"24","author":"H Zhang","year":"2000","unstructured":"Zhang H, Stickel M. Implementing the Davis-Putnam method. J Autom Reasoning, 2000, 24: 277\u2013296","journal-title":"J Autom Reasoning"},{"key":"4653_CR3","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1109\/SFCS.1991.185365","volume-title":"Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science","author":"C H Papadimitiou","year":"1991","unstructured":"Papadimitiou C H. On selecting a satisfying truth assignment. In: Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science. San Juan: IEEE Computer Society, 1991. 163\u2013169"},{"key":"4653_CR4","first-page":"440","volume-title":"Proceedings of 10th National Conference on Artificial Intelligence (AAAI-92)","author":"B Selman","year":"1992","unstructured":"Selman B, Levesque H, Mitchell D. A new method for solving hard satisfiability problems. In: Proceedings of 10th National Conference on Artificial Intelligence (AAAI-92). San Jose: AAAI Press, 1992. 440\u2013446"},{"key":"4653_CR5","first-page":"337","volume-title":"Proceedings of 12th National Conference on Artificial Intelligence (AAAI-94)","author":"B Selman","year":"1994","unstructured":"Selman B, Kautz H A, Cohen B. Noise strategies for improving local search. In: Proceedings of 12th National Conference on Artificial Intelligence (AAAI-94). Seattle: AAAI Press, 1994. 337\u2013343"},{"key":"4653_CR6","first-page":"410","volume-title":"Proceedings of the 40 th Annual Symposium on Foundation of Computer Science. New York","author":"U Sch\u00f6ning","year":"1999","unstructured":"Sch\u00f6ning U. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: Proceedings of the 40 th Annual Symposium on Foundation of Computer Science. New York, 1999. 410\u2013414"},{"key":"4653_CR7","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s10472-005-0421-9","volume":"43","author":"E A Hirsch","year":"2005","unstructured":"Hirsch E A, Kojevnikov A. UnitWalk: a new SAT solver that uses local search guided by unit clause elimination. Ann Math Artif Intel, 2005, 43: 91\u2013111","journal-title":"Ann Math Artif Intel"},{"key":"4653_CR8","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1126\/science.1073287","volume":"297","author":"M Mezard","year":"2002","unstructured":"Mezard M, Parisi G, Zecchina R. Analytic and algorithmic solution of random satisfiability problems. Science, 2002, 297: 812\u2013815","journal-title":"Science"},{"key":"4653_CR9","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.20057","volume":"27","author":"A Braunstein","year":"2005","unstructured":"Braunstein A, Mezard M, Zecchina R. Survey propagation: an algorithm for satisfiability. Random Struct Algor, 2005, 27: 201\u2013226","journal-title":"Random Struct Algor"},{"key":"4653_CR10","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"P Paturi","year":"2005","unstructured":"Paturi P, Pudlak P, Saks M E, et al. An improved exponential-time algorithm for k-SAT. J ACM, 2005, 52: 337\u2013364","journal-title":"J ACM"},{"key":"4653_CR11","doi-asserted-by":"crossref","first-page":"1248","DOI":"10.1137\/S0097539704440107","volume":"36","author":"M Alekhnovich","year":"2006","unstructured":"Alekhnovich M, Ben-Sasson E. Linear upper bounds for random walk on small density random 3-CNF. SIAM J Comput, 2006, 36: 1248\u20131263","journal-title":"SIAM J Comput"},{"key":"4653_CR12","first-page":"322","volume-title":"Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. Austin: Society for Industrial and Applied Mathematics","author":"A Broder","year":"1993","unstructured":"Broder A, Frieze A, Upeal E. On the satisfiability and maximum satisfiability of random 3-CNF formulas. In: Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. Austin: Society for Industrial and Applied Mathematics, 1993. 322\u2013330"},{"key":"4653_CR13","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1137\/1.9781611973068.50","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A Coja-Oghlan","year":"2009","unstructured":"Coja-Oghlan A, Feige U, Frieze A, et al. On smoothed k-CNF formulas and the Walksat algorithm. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. New York: Society for Industrial and Applied Mathematics, 2009. 451\u2013460"},{"key":"4653_CR14","first-page":"708","volume-title":"Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming","author":"A J Parkes","year":"2002","unstructured":"Parkes A J. Scaling properties of pure random walk on random 3-SAT. In: Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming. London: Springer-Verlag, 2002. 708\u2013713"},{"key":"4653_CR15","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/j.artint.2008.11.002","volume":"173","author":"Y Zhou","year":"2009","unstructured":"Zhou Y, He J, Nie Q. A comparative runtime analysis of heuristic algorithms for satisfiability problems. Artif Intell, 2009, 173: 240\u2013257","journal-title":"Artif Intell"},{"key":"4653_CR16","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1145\/800157.805047","volume-title":"Proceedings of the 3rd Annual ACM Symposium on Theory of Computing","author":"S Cook","year":"1971","unstructured":"Cook S. The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. New York: ACM Press, 1971. 151"},{"key":"4653_CR17","volume-title":"Computers and Intractability-a Guide to the Theory of NP-Completeness","author":"M R Garey","year":"1979","unstructured":"Garey M R, Johnson D S. Computers and Intractability-a Guide to the Theory of NP-Completeness. New York: Freeman, 1979"},{"key":"4653_CR18","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z","volume":"10","author":"A Frieze","year":"1997","unstructured":"Frieze A, McDiarmid C. Algorithm theory of random graphs. Random Struct algor, 1997, 10: 5\u201342","journal-title":"Random Struct algor"},{"key":"4653_CR19","volume-title":"Finite Markov Processes and their Applications. Chichester","author":"M Iosifescu","year":"1980","unstructured":"Iosifescu M. Finite Markov Processes and their Applications. Chichester. New York: John Wiley & Sons, 1980"},{"key":"4653_CR20","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0004-3702(02)00381-8","volume":"145","author":"J He","year":"2003","unstructured":"He J, Yao X. Towards an analytic framework for analyzing the computation time of evolutionary algorithms. Artif Intell, 2003, 145: 59\u201397","journal-title":"Artif Intell"}],"container-title":["Science China Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-012-4653-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11432-012-4653-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-012-4653-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T11:37:47Z","timestamp":1559389067000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11432-012-4653-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,17]]},"references-count":20,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["4653"],"URL":"https:\/\/doi.org\/10.1007\/s11432-012-4653-0","relation":{},"ISSN":["1674-733X","1869-1919"],"issn-type":[{"value":"1674-733X","type":"print"},{"value":"1869-1919","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,17]]}}}