{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T11:47:41Z","timestamp":1749124061970},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540646822"},{"type":"electronic","value":"9783540691068"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054372","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T03:43:28Z","timestamp":1149651808000},"page":"246-254","source":"Crossref","is-referenced-by-count":2,"title":["Local search algorithms for SAT: Worst-case analysis"],"prefix":"10.1007","author":[{"given":"Edward A.","family":"Hirsch","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"23_CR1","unstructured":"Dantsin, E.: Tautology proof systems based on the splitting method (in Russian). PhD thesis. Leningrad Division of Steklov Institute of Mathematics (LOMI) (1983)"},{"key":"23_CR2","unstructured":"Dantsin, E., Kreinovich, V.: Exponential upper bounds for the propositional satisfiability problem (in Russian). In: Proceedings of the 9th National Conference on Mathematical Logic. Leningrad (1988) p. 47"},{"key":"23_CR3","unstructured":"Franco, J., Swaminathan, R.: Average case results for satisfiability algorithms under the random clause model. Annals of Mathematics and Artificial Intelligence (to appear)"},{"key":"23_CR4","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. W. H. Freeman and Company, San Francisco (1979)"},{"key":"23_CR5","unstructured":"Gent, I., Walsh, T.: The Enigma of Hill-climbing Procedures for SAT. Research Paper 605, Department of Artificial Intelligence, University of Edinburgh (1992)"},{"key":"23_CR6","first-page":"28","volume-title":"Towards an Understanding of Hill-climbing Procedures for SAT","author":"I. Gent","year":"1993","unstructured":"Gent, I., Walsh, T.: Towards an Understanding of Hill-climbing Procedures for SAT. In: Proceedings of 11th National Conference on Artificial Intelligence. Washington, DC, AAAI Press (1993) 28\u201333"},{"key":"23_CR7","volume-title":"Hybrid Problems, Hybrid Solutions (AISB-95)","author":"I. Gent","year":"1995","unstructured":"Gent, I., Walsh, T.: Unsatisfied Variables in Local Search. In: Hallam, J. (ed.): Hybrid Problems, Hybrid Solutions (AISB-95). IOS Press, Amsterdam (1995)"},{"key":"23_CR8","unstructured":"Gu, J., Gu, Q.-P.: Average Time Complexity of The SAT1.2 Algorithm. In: Proceedings of the 5th Annual International Symposium on Algorithms and Computation (1994) 147\u2013155"},{"key":"23_CR9","unstructured":"Hirsch, E. A.: Two new upper bounds for SAT. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (1998) 521\u2013530"},{"issue":"1","key":"23_CR10","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(92)90029-U","volume":"43","author":"E. Koutsoupias","year":"1992","unstructured":"Koutsoupias, E., Papadimitriou, C. H.: On the greedy algorithm for satisfiability. Information Processing Letters 43(1) (1992) 53\u201355","journal-title":"Information Processing Letters"},{"key":"23_CR11","unstructured":"Kullmann, O.: Worst-case Analysis, 3-SAT Decision and Lower Bounds: Approaches for Improved SAT Algorithms. In: Du, D., Gu, J., Pardalos P.M. (eds.): DIMACS Proceedings SAT Workshop 1996. American Mathematical Society (1997)"},{"key":"23_CR12","first-page":"331","volume-title":"Proceedings of Frege Conference 1984. Schwerine","author":"H. Luckhardt","year":"1984","unstructured":"Luckhardt, H.: Obere Komplexit\u00c4tsschranken f\u00fcr TAUT-Entscheidungen. In: Proceedings of Frege Conference 1984. Schwerine, Akademie-Verlag Berline (1984) 331\u2013337"},{"key":"23_CR13","unstructured":"Monien, B., Speckenmeyer, E.: 3-satisfiability is testable in O(1.62r) steps. Bericht Nr. 3\/1979, Reihe Theoretische Informatik, Universit\u00c4t-Gesamthochschule-Paderborn"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Solving satisfiability in less than 2n steps. Discrete Applied Mathematics 10 (1985) 287\u2013295","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudlak, P., Zane, F.: Satisfiability Coding Lemma. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (1997) 566\u2013574","DOI":"10.1109\/SFCS.1997.646146"},{"key":"23_CR16","unstructured":"Schiermeyer, I.: Pure literal look ahead: An O(1.497n) 3-Satisfiability algorithm. In: Franco, J., Gallo, G., Kleine B\u00fcning, H., Speckenmeyer, E., Spera, C. (eds.): Workshop on the Satisfiability Problem, Technical Report. Siena, April, 29\u2013May, 3, 1996. University K\u00f6ln, Report No. 96-230"},{"key":"23_CR17","volume-title":"An Empirical Study of Greedy Local Search for Satisfiability Testing","author":"B. Selman","year":"1993","unstructured":"Selman, B., Kautz, H.: An Empirical Study of Greedy Local Search for Satisfiability Testing. In: Proceedings of the 11th Conference on Artificial Intelligence. Washington, DC, AAAI Press (1993)"},{"key":"23_CR18","unstructured":"Selman, B., Kautz, H.: Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search. In: Proceedings of the 14th Conference on Artificial Intelligence (1996)"},{"key":"23_CR19","first-page":"337","volume-title":"Noise strategies for improving local search","author":"B. Selman","year":"1993","unstructured":"Selman, B., Kautz, H., Cohen, B.: Noise strategies for improving local search. In: Proceedings of the 12th Conference on Artificial Intelligence. Seattle, Washington, AAAI Press (1993) 1:337\u2013343"},{"key":"23_CR20","first-page":"440","volume-title":"A new method for solving hard satisfiability problems","author":"B. Selman","year":"1992","unstructured":"Selman, B., Levesque, H., Mitchell, D.: A new method for solving hard satisfiability problems. In: Swartout, W. (ed.): Proceedings of the 10th Conference on Artificial Intelligence. San Jose, California, MIT Press (1992) 440\u2013446"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,10]],"date-time":"2019-02-10T18:22:32Z","timestamp":1549822952000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0054372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0054372","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}