{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T19:39:53Z","timestamp":1743017993540,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540875307"},{"type":"electronic","value":"9783540875314"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-87531-4_16","type":"book-chapter","created":{"date-parts":[[2008,8,30]],"date-time":"2008-08-30T08:40:53Z","timestamp":1220085653000},"page":"199-214","source":"Crossref","is-referenced-by-count":3,"title":["A Tight Karp-Lipton Collapse Result in Bounded Arithmetic"],"prefix":"10.1007","author":[{"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I","author":"J.L. Balc\u00e1zar","year":"1988","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, J.: Structural Complexity I. Springer, Heidelberg (1988)"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0304-3975(91)90160-4","volume":"84","author":"R. Beigel","year":"1991","unstructured":"Beigel, R.: Bounded queries to SAT and the Boolean hierarchy. Theoretical Computer Science\u00a084, 199\u2013223 (1991)","journal-title":"Theoretical Computer Science"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Chang, R., Fortnow, L.: One bit of advice. In: Proc. 20th Symposium on Theoretical Aspects of Computer Science, pp. 547\u2013558 (2003)","DOI":"10.1007\/3-540-36494-3_48"},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.jcss.2003.07.015","volume":"73","author":"J.-Y. Cai","year":"2007","unstructured":"Cai, J.-Y.: ${S}_2^p \\subseteq {ZPP}^{NP}$. Journal of Computer and System Sciences\u00a073(1), 25\u201335 (2007)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"16_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2005.01.002","volume":"198","author":"J.-Y. Cai","year":"2005","unstructured":"Cai, J.-Y., Chakaravarthy, V.T., Hemaspaandra, L.A., Ogihara, M.: Competing provers yield improved Karp-Lipton collapse results. Information and Computation\u00a0198(1), 1\u201323 (2005)","journal-title":"Information and Computation"},{"issue":"2","key":"16_CR6","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/S0097539790178069","volume":"25","author":"R. Chang","year":"1996","unstructured":"Chang, R., Kadin, J.: The Boolean hierarchy and the polynomial hierarchy: A closer connection. SIAM Journal on Computing\u00a025(2), 340\u2013354 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: Feasibly constructive proofs and the propositional calculus. In: Proc. 7th Annual ACM Symposium on Theory of Computing, pp. 83\u201397 (1975)","DOI":"10.1145\/800116.803756"},{"key":"16_CR8","unstructured":"Cook, S.A.: Theories for complexity classes and their propositional translations. In: Kraj\u00ed\u010dek, J. (ed.) Complexity of Computations and Proofs, pp. 175\u2013227. Quaderni di Matematica(2005)"},{"issue":"4","key":"16_CR9","doi-asserted-by":"publisher","first-page":"1353","DOI":"10.2178\/jsl\/1203350791","volume":"72","author":"S.A. Cook","year":"2007","unstructured":"Cook, S.A., Kraj\u00ed\u010dek, J.: Consequences of the provability of NP\u2009\u2286\u2009P\/poly. The Journal of Symbolic Logic\u00a072(4), 1353\u20131371 (2007)","journal-title":"The Journal of Symbolic Logic"},{"key":"16_CR10","unstructured":"Cook, S.A., Nguyen, P.: Foundations of proof complexity: Bounded arithmetic and propositional translations (Book in progress), http:\/\/www.cs.toronto.edu\/~sacook"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook, S.A., Reckhow, R.A.: The relative efficiency of propositional proof systems. The Journal of Symbolic Logic\u00a044, 36\u201350 (1979)","journal-title":"The Journal of Symbolic Logic"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Klivans, A.R.: NP with small advice. In: Proc. 20th Annual IEEE Conference on Computational Complexity, pp. 228\u2013234 (2005)","DOI":"10.1109\/CCC.2005.15"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Je\u0159\u00e1bek, E.: Approximate counting by hashing in bounded arithmetic (preprint, 2007)","DOI":"10.2178\/jsl\/1191333850"},{"issue":"6","key":"16_CR14","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0217080","volume":"17","author":"J. Kadin","year":"1988","unstructured":"Kadin, J.: The polynomial time hierarchy collapses if the Boolean hierarchy collapses. SIAM Journal on Computing\u00a017(6), 1263\u20131282 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR15","first-page":"302","volume-title":"Proc. 12th ACM Symposium on Theory of Computing","author":"R.M. Karp","year":"1980","unstructured":"Karp, R.M., Lipton, R.J.: Some connections between nonuniform and uniform complexity classes. In: Proc. 12th ACM Symposium on Theory of Computing, pp. 302\u2013309. ACM Press, New York (1980)"},{"issue":"1","key":"16_CR16","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1137\/S0097539795296206","volume":"28","author":"J. K\u00f6bler","year":"1998","unstructured":"K\u00f6bler, J., Watanabe, O.: New collapse consequences of NP having small circuits. SIAM Journal on Computing\u00a028(1), 311\u2013324 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR17","series-title":"Encyclopedia of Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511529948","volume-title":"Bounded Arithmetic, Propositional Logic, and Complexity Theory","author":"J. Kraj\u00ed\u010dek","year":"1995","unstructured":"Kraj\u00ed\u010dek, J.: Bounded Arithmetic, Propositional Logic, and Complexity Theory. Encyclopedia of Mathematics and Its Applications, vol.\u00a060. Cambridge University Press, Cambridge (1995)"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.2307\/2274765","volume":"54","author":"J. Kraj\u00ed\u010dek","year":"1989","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P.: Propositional proof systems, the consistency of first order theories and the complexity of computations. The Journal of Symbolic Logic\u00a054, 1063\u20131079 (1989)","journal-title":"The Journal of Symbolic Logic"},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0168-0072(91)90043-L","volume":"52","author":"J. Kraj\u00ed\u010dek","year":"1991","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P., Takeuti, G.: Bounded arithmetic and the polynomial hierarchy. Annals of Pure and Applied Logic\u00a052, 143\u2013153 (1991)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"1","key":"16_CR20","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0304-3975(01)00155-4","volume":"288","author":"Z. Sadowski","year":"2002","unstructured":"Sadowski, Z.: On an optimal propositional proof system and the structure of easy subsets of TAUT. Theoretical Computer Science\u00a0288(1), 181\u2013193 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"16_CR21","doi-asserted-by":"publisher","first-page":"942","DOI":"10.2307\/2275794","volume":"61","author":"D. Zambella","year":"1996","unstructured":"Zambella, D.: Notes on polynomially bounded arithmetic. The Journal of Symbolic Logic\u00a061(3), 942\u2013966 (1996)","journal-title":"The Journal of Symbolic Logic"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87531-4_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T19:04:35Z","timestamp":1738350275000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-87531-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540875307","9783540875314"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87531-4_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}