{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T03:18:23Z","timestamp":1778296703366,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540249986","type":"print"},{"value":"9783540318569","type":"electronic"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_3","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T18:06:19Z","timestamp":1267553179000},"page":"36-43","source":"Crossref","is-referenced-by-count":28,"title":["Algorithmics in Exponential Time"],"prefix":"10.1007","author":[{"given":"Uwe","family":"Sch\u00f6ning","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"3_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear time algorithm for testing the truth of certain quantified Boolean formulas. Information Processing Letters\u00a08(3), 121\u2013123 (1979)","journal-title":"Information Processing Letters"},{"key":"3_CR2","volume-title":"Information Theory","author":"R.B. Ash","year":"1965","unstructured":"Ash, R.B.: Information Theory. Dover, New York (1965)"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-24605-3_12","volume-title":"Theory and Applications of Satisfiability Testing","author":"S. Baumer","year":"2004","unstructured":"Baumer, S., Schuler, R.: Improving a probabilistic 3-SAT algorithm by dynamic search and independent clause pairs. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 150\u2013161. Springer, Heidelberg (2004)"},{"key":"3_CR4","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1109\/SFCS.1995.492575","volume-title":"Proceedings of the 36nd Annual IEEE Symposium on Foundations of Computer Science","author":"R. Beigel","year":"1995","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time O(1:3446 n ): a no-MIS algorithm. In: Proceedings of the 36nd Annual IEEE Symposium on Foundations of Computer Science, pp. 444\u2013452. IEEE, Los Alamitos (1995)"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Brueggemann, T., Kern, W.: An improved local search algorithm for 3-SAT. Memorandum No. 1709, Department of Applied Mathematics, University of Twente (2004)","DOI":"10.1016\/j.tcs.2004.08.002"},{"key":"3_CR6","volume-title":"Covering Codes","author":"G. Cohen","year":"1997","unstructured":"Cohen, G., Honkala, I., Litsyn, S., Lobstein, A.: Covering Codes. North-Holland, Amsterdam (1997)"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/3-540-45022-X_21","volume-title":"Automata, Languages and Programming","author":"E. Dantsin","year":"2000","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Sch\u00f6ning, U.: Deterministic algorithms for k-SAT based on covering codes and local search. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 236\u2013247. Springer, Heidelberg (2000)"},{"key":"3_CR8","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A deterministic $(2-\\frac{2}{k+1})^{n}$ algorithm for k-SAT based on local search. To appear in Theoretical Computer Science"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/3-540-45841-7_15","volume-title":"STACS 2002","author":"T. Hofmeister","year":"2002","unstructured":"Hofmeister, T., Sch\u00f6ning, U., Schuler, R., Watanabe, O.: A probabilistic 3-SAT algorithm further improved. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 193\u2013202. Springer, Heidelberg (2002)"},{"key":"#cr-split#-3_CR10.1","unstructured":"Iwama, K., Tamaki, S.: Improved upper bounds for 3-SAT. Electronic Colloquium on Computational Complexity. Report No. 53 (2003)"},{"key":"#cr-split#-3_CR10.2","unstructured":"Also in: Proceedings of the fifteenth annual ACM-SIAM Symposium on Discrete algorithms, p. 328. ACM, New York (2004)"},{"key":"3_CR11","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 2 n steps. Discrete Applied Mathematics\u00a010, 287\u2013295 (1985)","journal-title":"Discrete Applied Mathematics"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: On selecting a satisfying truth assignment. In: Proceedings of the 32nd Ann. IEEE Symp. on Foundations of Computer Science, pp. 163\u2013169 (1991)","DOI":"10.1109\/SFCS.1991.185365"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e1k, P., Zane, F.: Satisfiability coding lemma. In: Proceedings 38th IEEE Symposium on Foundations of Computer Science 1997, pp. 566\u2013574 (1997)","DOI":"10.1109\/SFCS.1997.646146"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-SAT. In: Proceedings 39th IEEE Symposium on Foundations of Computer Science 1998, pp. 628\u2013637 (1998)","DOI":"10.1109\/SFCS.1998.743513"},{"key":"3_CR15","first-page":"29","volume-title":"Proceedings of the 27th Annual Symposium on Foundations of Computer Science","author":"M. Saks","year":"1986","unstructured":"Saks, M., Wigderson, A.: Probabilistic boolean decision trees and the complexity of evaluating game trees. In: Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pp. 29\u201338. IEEE Computer Science Press, Los Alamitos (1986)"},{"key":"3_CR16","unstructured":"Sch\u00f6ning, U.: On The Complexity of Constraint Satisfaction Problems. Ulmer Informatik-Berichte, Nr. 99-03. Universit\u00e4t Ulm, Fakult\u00e4t f\u00fcr Informatik (1999)"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: Proceedings 40th IEEE Symposium on Foundations of Computer Science 1999, pp. 410\u2013414 (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"issue":"4","key":"3_CR18","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s00453-001-0094-7","volume":"32","author":"U. Sch\u00f6ning","year":"2002","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica\u00a032(4), 615\u2013623 (2002)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","STACS 2005"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T23:10:08Z","timestamp":1739920208000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}