{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T08:38:31Z","timestamp":1742978311473,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642174926"},{"type":"electronic","value":"9783642174933"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17493-3_7","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T13:41:01Z","timestamp":1291383661000},"page":"50-59","source":"Crossref","is-referenced-by-count":4,"title":["On the Exact Complexity of Evaluating Quantified k-CNF"],"prefix":"10.1007","author":[{"given":"Chris","family":"Calabro","sequence":"first","affiliation":[]},{"given":"Russell","family":"Impagliazzo","sequence":"additional","affiliation":[]},{"given":"Ramamohan","family":"Paturi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"7_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. Inf. Process. Lett.\u00a08(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"7_CR2","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1006\/inco.1995.1025","volume":"117","author":"H.K. B\u00fcning","year":"1995","unstructured":"B\u00fcning, H.K., Karpinski, M., Fl\u00f6gel, A.: Resolution for quantified boolean formulas. Information and Computation\u00a0117(1), 12\u201318 (1995)","journal-title":"Information and Computation"},{"issue":"3","key":"7_CR3","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/j.ic.2008.11.001","volume":"207","author":"H. Chen","year":"2009","unstructured":"Chen, H.: Existentially restricted quantified constraint satisfaction. Information and Computation\u00a0207(3), 369\u2013388 (2009)","journal-title":"Information and Computation"},{"key":"#cr-split#-7_CR4.1","doi-asserted-by":"crossref","unstructured":"Calabro, C., Impagliazzo, R., Kabanets, V., Paturi, R.: The complexity of unique k-sat: An isolation lemma for k-cnfs. Journal of Computer and Systems Sciences??74(3), 386???393 (2008);","DOI":"10.1016\/j.jcss.2007.06.015"},{"key":"#cr-split#-7_CR4.2","unstructured":"Preliminary version in Proceedings of the Eighteenth IEEE Conference on Computational Complexity, pp. 135???144 (2003)"},{"key":"7_CR5","first-page":"252","volume-title":"CCC 2006: Proceedings of the 21st Annual IEEE Conference on Computational Complexity","author":"C. Calabro","year":"2006","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: A duality between clause width and clause density for SAT. In: CCC 2006: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, Washington, DC, USA, pp. 252\u2013260. IEEE Computer Society, Los Alamitos (2006)"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","volume-title":"Parameterized and Exact Computation: 4th International Workshop, IWPEC 2009, Revised Selected Papers, Copenhagen, Denmark","author":"C. Calabro","year":"2009","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Parameterized and Exact Computation: 4th International Workshop, IWPEC 2009, Revised Selected Papers, Copenhagen, Denmark, September 10-11, pp. 75\u201385. Springer, Heidelberg (2009)"},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/11499107_31","volume-title":"Theory and Applications of Satisfiability Testing","author":"E. Dantsin","year":"2005","unstructured":"Dantsin, E., Wolpert, A.: An improved upper bound for SAT. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol.\u00a03569, pp. 400\u2013407. Springer, Heidelberg (2005)"},{"key":"#cr-split#-7_CR8.1","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R.: The complexity of k-sat. Journal of Computer and Systems Sciences??62(2), 367???375 (2001);","DOI":"10.1006\/jcss.2000.1727"},{"key":"#cr-split#-7_CR8.2","unstructured":"Preliminary version in 14th Annual IEEE Conference on Computational Complexity, pp. 237???240 (1999)"},{"key":"#cr-split#-7_CR9.1","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences??63, 512???530 (1998);","DOI":"10.1006\/jcss.2001.1774"},{"key":"#cr-split#-7_CR9.2","unstructured":"Preliminary version in 39th Annual IEEE Symposium on Foundations of Computer Science, pp 653???662 (1998)"},{"key":"#cr-split#-7_CR10.1","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl??k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-sat. Journal of the ACM??52(3), 337???364 (2005);","DOI":"10.1145\/1066100.1066101"},{"key":"#cr-split#-7_CR10.2","unstructured":"Preliminary version in 39th Annual IEEE Symposium on Foundations of Computer Science, pp. 628???637 (1998)"},{"key":"#cr-split#-7_CR11.1","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl??k, P., Zane, F.: Satisfiability coding lemma. Chicago Journal of Theoretical Computer Science (December 1999);","DOI":"10.4086\/cjtcs.1999.011"},{"key":"#cr-split#-7_CR11.2","unstructured":"Preliminary version in 38th Annual Symposium on Foundations of Computer Science, pp. 566???574 (1997)"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Rolf, D.: Improved bound for the PPSZ\/Sch\u00f6ning-algorithm for 3-sat. Electronic Colloquium on Computational Complexity (ECCC) 12(159) (2005)","DOI":"10.3233\/SAT190005"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-sat and constraint satisfaction problems. In: FOCS, pp. 410\u2013414 (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"issue":"1","key":"7_CR14","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.jalgor.2004.04.012","volume":"54","author":"R. Schuler","year":"2005","unstructured":"Schuler, R.: An algorithm for the satisfiability problem of formulas in conjunctive normal form. Journal of Algorithms\u00a054(1), 40\u201344 (2005)","journal-title":"Journal of Algorithms"},{"key":"7_CR15","unstructured":"Williams, R.: Algorithms for quantified boolean formulas. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 299\u2013307 (2002)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17493-3_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T12:01:53Z","timestamp":1740744113000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17493-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642174926","9783642174933"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17493-3_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}