{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:21:09Z","timestamp":1726410069793},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642382321"},{"type":"electronic","value":"9783642382338"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38233-8_10","type":"book-chapter","created":{"date-parts":[[2013,5,15]],"date-time":"2013-05-15T12:57:16Z","timestamp":1368622636000},"page":"110-121","source":"Crossref","is-referenced-by-count":0,"title":["Exponential Complexity of Satisfiability Testing for Linear-Size Boolean Formulas"],"prefix":"10.1007","author":[{"given":"Evgeny","family":"Dantsin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Wolpert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"10_CR1","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.jcss.2008.10.003","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Fellows, M.R., Thilikos, D.M.: Derivation of algorithms for cutwidth and related graph layout parameters. Journal of Computer and System Sciences\u00a075(4), 231\u2013244 (2009)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNF-Sat. In: Proceedings of the 27th Annual IEEE Conference on Computational Complexity, CCC 2012, pp. 74\u201384. IEEE Computer Society (2012)","DOI":"10.1109\/CCC.2012.36"},{"key":"10_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","volume-title":"Parameterized and Exact Computation","author":"C. Calabro","year":"2009","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 75\u201385. Springer, Heidelberg (2009)"},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-642-03351-3_8","volume-title":"Computer Science - Theory and Applications","author":"C. Calabro","year":"2009","unstructured":"Calabro, C., Paturi, R.: k-SAT is no harder than Decision-Unique-k-SAT. In: Frid, A., Morozov, A., Rybalchenko, A., Wagner, K.W. (eds.) CSR 2009. LNCS, vol.\u00a05675, pp. 59\u201370. Springer, Heidelberg (2009)"},{"key":"10_CR5","unstructured":"Dantsin, E., Hirsch, E.A.: Worst-case upper bounds. In: Handbook of Satisfiability, ch.12, pp. 403\u2013424. IOS Press (2009)"},{"issue":"2","key":"10_CR6","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. Journal of Computer and System Sciences\u00a062(2), 367\u2013375 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"10_CR7","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. Journal of Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e1k, P.: On the complexity of circuit satisfiability. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, STOC 2010, pp. 241\u2013250. ACM (2010)","DOI":"10.1145\/1806689.1806724"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Pudl\u00e1k, P.: The length of proofs. In: Buss, S.R. (ed.) Handbook of Proof Theory, pp. 547\u2013637. Elsevier (1998)","DOI":"10.1016\/S0049-237X(98)80023-2"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Santhanam, R.: Fighting perebor: New and improved algorithms for formula and QBF satisfiability. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pp. 183\u2013192 (2010)","DOI":"10.1109\/FOCS.2010.25"},{"key":"10_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1007\/978-3-642-31594-7_65","volume-title":"Automata, Languages, and Programming","author":"R. Santhanam","year":"2012","unstructured":"Santhanam, R., Srinivasan, S.: On the Limits of Sparsification. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 774\u2013785. Springer, Heidelberg (2012)"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Seto, K., Tamaki, S.: A satisfiability algorithm and average-case hardness for formulas over the full binary basis. In: Proceedings of the 27th Annual IEEE Conference on Computational Complexity, CCC 2012, pp. 107\u2013116. IEEE Computer Society (2012)","DOI":"10.1109\/CCC.2012.29"},{"key":"#cr-split#-10_CR13.1","doi-asserted-by":"crossref","unstructured":"Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: Slisenko, A.O. (ed.) Studies in Constructive Mathematics and Mathematical Logic, Part II, pp. 115-125 (1968) (in Russian)","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"#cr-split#-10_CR13.2","doi-asserted-by":"crossref","unstructured":"Reprinted in: Siekmann, J., Wrightson, G. (eds.): Automation of Reasoning 2: Classical Papers on Computational Logic 1967-1970, pp. 466-483. Springer (1983)","DOI":"10.1007\/978-3-642-81955-1"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer (1999)","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38233-8_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,1]],"date-time":"2023-07-01T19:18:55Z","timestamp":1688239135000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38233-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642382321","9783642382338"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38233-8_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}