{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T05:29:56Z","timestamp":1736573396785,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648277"},{"type":"electronic","value":"9783540685326"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"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":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055762","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T17:36:31Z","timestamp":1155836191000},"page":"129-141","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Satisfiability \u2014 Algorithms and logic"],"prefix":"10.1007","author":[{"given":"Pavel","family":"Pudl\u00e1k","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"P. Beame, R. Karp, T. Pitassi and M. Saks, On the complexity of unsatisfiability proofs for random k-CNF formulas, Proc. 30-th STOC, 1998, to appear.","DOI":"10.1145\/276698.276870"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"S.A. Cook, The complexity of theorem proving procedures, Proc. 3-rd STOC, 1971, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"issue":"1","key":"9_CR3","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"S.A. Cook and A.R. Reckhow, The relative efficiency of propositional proof systems, J. of Symbolic Logic 44(1), 1979, 36\u201350.","journal-title":"J. of Symbolic Logic"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"M. Davis, G. Logemann and D. Loveland, A machine program for theorem proving, Communications of the ACM 5, 1962, 394\u2013397.","journal-title":"Communications of the ACM"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"L.K. Grover, A fast quantum mechanical algorithm for database search, Proc. 28-th STOC 1996, 212\u2013218.","DOI":"10.1145\/237814.237866"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"A. Haken, The intractability of resolution, Theor. Computer Science, 39, 1985, 297\u2013308.","journal-title":"Theor. Computer Science"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Almost optimal lower bounds for small depth circuits, Proc. 18-th STOC, 1986, 6\u201320.","DOI":"10.1145\/12130.12132"},{"key":"9_CR8","unstructured":"E.A. Hirsch, Two new upper bounds for SAT, Proc. 9-th SODA, 1998, to appear."},{"key":"9_CR9","unstructured":"R. Impagliazzo, P. Pudl\u00e1k and J. Sgall, Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm, to appear in Computational Complexity."},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"J. Kraj\u00ed\u010dek, Bounded arithmetic, propositional logic, and complexity theory, Cambridge Univ. Press 1995.","DOI":"10.1017\/CBO9780511529948"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"B. Monien and E. Speckenmeyer, Solving satisfiability in less than 2n steps, Discrete Applied Math. 10, 1985, 287\u2013295.","journal-title":"Discrete Applied Math."},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"R. Paturi, P. Pudl\u00e1k and F. Zane, Satisfiability coding lemma, Proc. 38-th FOCS, 1997, 566\u2013574.","DOI":"10.1109\/SFCS.1997.646146"},{"key":"9_CR13","unstructured":"R. Paturi, P. Pudl\u00e1k, M.E. Saks and F. Zane, An improved exponential-time algorithm for k-SAT, preprint, 1998."},{"issue":"3","key":"9_CR14","doi-asserted-by":"publisher","first-page":"981","DOI":"10.2307\/2275583","volume":"62","author":"P. Pudl\u00e1k","year":"1997","unstructured":"P. Pudl\u00e1k, Lower bounds for resolution and cutting planes proofs and monotone computations, J. of Symb. Logic 62(3), 1997, 981\u2013998.","journal-title":"J. of Symb. Logic"},{"key":"9_CR15","unstructured":"A. A. Razborov, Lower bounds for the polynomial calculus, to appear in Computational Complexity."},{"key":"9_CR16","first-page":"379","volume":"702","author":"I. Schiermeyer","year":"1993","unstructured":"I. Schiermeyer, Solving 3-Satisfiability in less than 1.579n steps, CSL'92, LNCS 702, 1993, 379\u2013394.","journal-title":"LNCS"},{"key":"9_CR17","unstructured":"I. Schiermeyer, Pure literal look ahead: An O(1.497n) 3-satisfiability algorithm, preprint, 1996."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"G.C. Tseitin, On the complexity of derivations in propositional calculus, Studies in mathematics and mathematical logic, Part II, ed. A.O. Slisenko, 1968, 115\u2013125.","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/7531.8928","volume":"34","author":"A. Urquhart","year":"1987","unstructured":"A. Urquhart, Hard examples for resolution, J. of ACM 34, 1987, 209\u2013219.","journal-title":"J. of ACM"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055762","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T13:52:43Z","timestamp":1736517163000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055762"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0055762","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"28 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}