{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:28:35Z","timestamp":1764782915308},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540634379"},{"type":"electronic","value":"9783540695479"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0029974","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T01:24:59Z","timestamp":1133400299000},"page":"309-318","source":"Crossref","is-referenced-by-count":26,"title":["Complexity of finding short resolution proofs"],"prefix":"10.1007","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"31_CR1","unstructured":"R. Beigel and D. Eppstein. 3-coloring in time O(1.3446n): a no-MIS algorithm. Proc. 36th IEEE Symp. on Foundations of Computer Science, pages 444\u2013452, 1995."},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"P. Beame and T. Pitassi. Simplified and improved resolution lower bounds. Proc. 37th IEEE Symp. on Foundations of Computer Science, 1996.","DOI":"10.1109\/SFCS.1996.548486"},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"M. Clegg, J. Edmonds, and R. Impagliazzo. Using the Groebner basis algorithm to find proofs of unsatisfiability. Proc. 28th ACM Symposium on Theory of Computing, pages 174\u2013183, 1996.","DOI":"10.1145\/237814.237860"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(91)90315-S","volume":"81","author":"O. Dubois","year":"1991","unstructured":"O. Dubois. Counting the number of solutions for instances of satisfiability. Theor. Comput. Sci., 81:49\u201364, 1991.","journal-title":"Theor. Comput. Sci."},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"A. Haken. The intractability of resolution. Theor. Compout. Sci., pages 297\u2013308, 1985.","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"K. Iwama and E. Miyano. Intractability of read-once resolution. In Proc. 10th IEEE Structure in Complexity Conference, 1995.","DOI":"10.1109\/SCT.1995.514725"},{"key":"31_CR7","doi-asserted-by":"crossref","first-page":"847","DOI":"10.1109\/TC.1986.1676847","volume":"C-35","author":"T. Ran","year":"1986","unstructured":"T. Ran. An O(20.304n\n) algorithm for solving maximum independent set problem. IEEE Trans. Comput., C-35:847\u2013851, 1986.","journal-title":"IEEE Trans. Comput."},{"key":"31_CR8","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 Appl. Math., 10:287\u2013295, 1985.","journal-title":"Discrete Appl. Math."},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J. Robson","year":"1986","unstructured":"J. Robson. Algorithms for maximum independent sets. J. Algr., 7:425\u2013440, 1986.","journal-title":"J. Algr."},{"key":"31_CR10","doi-asserted-by":"crossref","unstructured":"I. Schiermeyer. Solving 3-satisfiability in less than 1.579n steps. 6th Worksh. Computer Science Logic, pages 379\u2013394, 1993.","DOI":"10.1007\/3-540-56992-8_22"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1997"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029974","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,6]],"date-time":"2019-02-06T01:23:13Z","timestamp":1549416193000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029974"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540634379","9783540695479"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/bfb0029974","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}