{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T16:10:30Z","timestamp":1740327030912,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540208518"},{"type":"electronic","value":"9783540246053"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24605-3_6","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T08:50:35Z","timestamp":1280393435000},"page":"69-77","source":"Crossref","is-referenced-by-count":1,"title":["Density Condensation of Boolean Formulas"],"prefix":"10.1007","author":[{"given":"Youichi","family":"Hanatani","sequence":"first","affiliation":[]},{"given":"Takashi","family":"Horiyama","sequence":"additional","affiliation":[]},{"given":"Kazuo","family":"Iwama","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"6_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":"6_CR2","doi-asserted-by":"crossref","unstructured":"Baumer, S., Schuler, R.: Improving a probabilistic 3-SAT Algorithm by Dynamic Search and Independent Clause Pairs. In: Proc. 6th International Coference on Theory and Applications of Satisfiability Testing, pp. 36\u201344 (2003)","DOI":"10.1007\/978-3-540-24605-3_12"},{"issue":"1","key":"6_CR3","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E. Dantsin","year":"2002","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A Deterministic (2\u20132\/(k+1)) n Algorithm for k-SAT Based on Local Search. Theoretical Computer Science\u00a0289(1), 69\u201383 (2002)","journal-title":"Theoretical Computer Science"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.: A Machine Program for Theorem-Proving. Comm. ACM\u00a05, 394\u2013397 (1962)","journal-title":"Comm. ACM"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"Davis, M., Putnam, H.: A Computing Procedure for Quantification Theory. J. ACM\u00a07, 201\u2013215 (1960)","journal-title":"J. ACM"},{"issue":"3","key":"6_CR6","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1006\/jagm.1996.0062","volume":"21","author":"M.L. Fredman","year":"1996","unstructured":"Fredman, M.L., Khachiyan, L.: On the Complexity of Dualization of Monotone Disjunctive Normal Forms. J. Algorithms\u00a021(3), 618\u2013628 (1996)","journal-title":"J. Algorithms"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Hormeister, T., Sch\u00f6ning, U., Schuler, R., Watanabe, O.: Probabilistic 3-SAT Algorithm Further Improved. In: Proc. 10th Symposium on Theoretical Aspects of Computer Science. LNCS, vol.\u00a02285, pp. 193\u2013202 (2002)","DOI":"10.1007\/3-540-45841-7_15"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BFb0029974","volume-title":"Mathematical Foundations of Computer Science 1997","author":"K. Iwama","year":"1997","unstructured":"Iwama, K.: Complexity of Finding Short Resolution Proofs. In: Privara, I., Ru\u017ei\u010dka, P. (eds.) MFCS 1997. LNCS, vol.\u00a01295, pp. 309\u2013318. Springer, Heidelberg (1997)"},{"key":"6_CR9","unstructured":"Monien, B., Speckenmeyer, E.: 3-Satisfiability is Testable in O(1.62 r ) Steps. Technical Report Bericht Nr. 3\/1979, Universit\u00e4t-Gesamthochschule-Paderborn, Reihe Theoretische Informatik (1979)"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/0022-0000(88)90042-6","volume":"37","author":"C.H. Papadimitriou","year":"1988","unstructured":"Papadimitriou, C.H., Wolfe, D.: The Complexity of Facets Resolved. J. Computers and System Sciences\u00a037, 2\u201313 (1988)","journal-title":"J. Computers and System Sciences"},{"key":"6_CR11","unstructured":"Schiermeyer,I.: Pure Literal Look Ahead: An O(1.497 n ) 3-Satisability Algorithm. In: Proc. the Workshop on the Satisability Problem, pp. 63\u201372 (1996)"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems. In: Proc. 40th Annual Symposium on Foundations of Computer Science, pp. 410\u2013414 (1999)","DOI":"10.1109\/SFFCS.1999.814612"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24605-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T15:30:15Z","timestamp":1740324615000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24605-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540208518","9783540246053"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24605-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}