{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:58:46Z","timestamp":1725562726286},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642152047"},{"type":"electronic","value":"9783642152054"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15205-4_3","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T14:48:24Z","timestamp":1281710904000},"page":"22-31","source":"Crossref","is-referenced-by-count":0,"title":["From Feasible Proofs to Feasible Computations"],"prefix":"10.1007","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S. Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"issue":"6","key":"3_CR2","doi-asserted-by":"publisher","first-page":"1939","DOI":"10.1137\/S0097539798353230","volume":"29","author":"M.L. Bonet","year":"2000","unstructured":"Bonet, M.L., Pitassi, T., Raz, R.: On Interpolation and Automatization for Frege Proof Systems. SIAM J. of Computing\u00a029(6), 1939\u20131967 (2000)","journal-title":"SIAM J. of Computing"},{"key":"3_CR3","volume-title":"Bounded Arithmetic","author":"S.R. Buss","year":"1986","unstructured":"Buss, S.R.: Bounded Arithmetic. Naples, Bibliopolis (1986)"},{"issue":"3","key":"3_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1112\/plms\/s3-69.1.1","volume":"69","author":"S.R. Buss","year":"1994","unstructured":"Buss, S.R., Kraj\u00ed\u010dek, J.: An application of boolean complexity to separation problems in bounded arithmetic. Proceedings of the London Mathematical Society\u00a069(3), 1\u201321 (1994)","journal-title":"Proceedings of the London Mathematical Society"},{"key":"3_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04943-3","volume-title":"Boolean Functions and Models of Computation","author":"P. Clote","year":"2002","unstructured":"Clote, P., Kranakis, E.: Boolean Functions and Models of Computation. Springer, Heidelberg (2002)"},{"key":"3_CR6","first-page":"24","volume-title":"Proc. Logic, Methodology and Philosophy of Science","author":"A. Cobham","year":"1965","unstructured":"Cobham, A.: The intrinsic computational difficulty of functions. In: Bar-Hillel, Y. (ed.) Proc. Logic, Methodology and Philosophy of Science, pp. 24\u201330. North-Holland, Amsterdam (1965)"},{"key":"3_CR7","first-page":"83","volume-title":"Proc. 7 $^{\\mbox{th}}$ Annual ACM Symp. on Theory of Computing","author":"S.A. Cook","year":"1975","unstructured":"Cook, S.A.: Feasibly constructive proofs and the propositional calculus. In: Proc. 7 $^{\\mbox{th}}$ Annual ACM Symp. on Theory of Computing, pp. 83\u201397. ACM Press, New York (1975)"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Nguyen, P.: Logical foundations of proof complexity. Cambridge U. Press, Cambridge (2009)","DOI":"10.1017\/CBO9780511676277"},{"issue":"1","key":"3_CR9","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook, S.A., Reckhow: The relative efficiency of propositional proof systems. J. Symbolic Logic\u00a044(1), 36\u201350 (1979)","journal-title":"J. Symbolic Logic"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.apal.2003.12.003","volume":"129","author":"E. Je\u0159\u00e1bek","year":"2004","unstructured":"Je\u0159\u00e1bek, E.: Dual weak pigeonhole principle, Boolean complexity, and derandomization. Annals of Pure and Applied Logic\u00a0129, 1\u201337 (2004)","journal-title":"Annals of Pure and Applied Logic"},{"key":"3_CR11","unstructured":"Kolodziejczyk, L., Nguyen, P., Thapen, N.: The provably total NP search problems of weak second order bounded arithmetic (2009) (preprint)"},{"issue":"2","key":"3_CR12","doi-asserted-by":"publisher","first-page":"587","DOI":"10.2307\/2154418","volume":"338","author":"J. Kraj\u00ed\u010dek","year":"1993","unstructured":"Kraj\u00ed\u010dek, J.: Fragments of bounded arithmetic and bounded query classes. Transactions of the A.M.S.\u00a0338(2), 587\u2013598 (1993)","journal-title":"Transactions of the A.M.S."},{"key":"3_CR13","doi-asserted-by":"crossref","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)","DOI":"10.1017\/CBO9780511529948"},{"issue":"6","key":"3_CR14","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1007\/s00153-005-0279-x","volume":"44","author":"J. Kraj\u00ed\u010dek","year":"2005","unstructured":"Kraj\u00ed\u010dek, J.: Hardness assumptions in the foundations of theoretical computer science. Archive for Mathematical Logic\u00a044(6), 667\u2013675 (2005)","journal-title":"Archive for Mathematical Logic"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.4171\/009-1\/14","volume-title":"European congress of mathematics (ECM), Stockholm, Sweden","author":"J. Kraj\u00ed\u010dek","year":"2005","unstructured":"Kraj\u00ed\u010dek, J.: Proof complexity. In: Laptev, A. (ed.) European congress of mathematics (ECM), Stockholm, Sweden, June 27-July 2, pp. 221\u2013231. European Mathematical Society, Zurich (2005)"},{"issue":"2","key":"3_CR16","doi-asserted-by":"publisher","first-page":"774","DOI":"10.2178\/jsl\/1268917504","volume":"75","author":"J. Kraj\u00ed\u010dek","year":"2010","unstructured":"Kraj\u00ed\u010dek, J.: A form of feasible interpolation for constant depth Frege systems. J. of Symbolic Logic\u00a075(2), 774\u2013784 (2010)","journal-title":"J. of Symbolic Logic"},{"key":"3_CR17","unstructured":"Kraj\u00ed\u010dek, J.: On the proof complexity of the Nisan-Wigderson generator based on a hard $\\mbox{NP } \\cap \\mbox{ coNP}$ function (submitted, March 2010) (preprint); Preliminary version in Electronic Colloquium on Computational Complexity, Rep. No.54 (2010)"},{"issue":"3","key":"3_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. J. Symbolic Logic\u00a054(3), 1063\u20131079 (1989)","journal-title":"J. Symbolic Logic"},{"issue":"1","key":"3_CR19","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1002\/malq.19900360106","volume":"36","author":"J. Kraj\u00ed\u010dek","year":"1990","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P.: Quantified Propositional Calculi and Fragments of Bounded Arithmetic. Zeitschr. f. Mathematikal Logik u. Grundlagen d. Mathematik, Bd.\u00a036(1), 29\u201346 (1990)","journal-title":"Zeitschr. f. Mathematikal Logik u. Grundlagen d. Mathematik, Bd."},{"issue":"1","key":"3_CR20","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1006\/inco.1997.2674","volume":"140","author":"J. Kraj\u00ed\u010dek","year":"1998","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P.: Some consequences of cryptographical conjectures for $S^1_2$ and EF. Information and Computation\u00a0140(1), 82\u201394 (1998)","journal-title":"Information and Computation"},{"key":"3_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/BFb0029595","volume-title":"Mathematical Foundations of Computer Science 1990","author":"J. Kraj\u00ed\u010dek","year":"1990","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P., Sgall, J.: Interactive Computations of Optimal Solutions. In: Rovan, B. (ed.) MFCS 1990. LNCS, vol.\u00a0452, pp. 48\u201360. Springer, Heidelberg (1990)"},{"key":"3_CR22","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":"2","key":"3_CR23","doi-asserted-by":"publisher","first-page":"649","DOI":"10.2178\/jsl\/1185803628","volume":"72","author":"J. Kraj\u00ed\u010dek","year":"2007","unstructured":"Kraj\u00ed\u010dek, J., Skelley, A., Thapen, N.: NP search problems in low fragments of bounded arithmetic. J. of Symbolic Logic\u00a072(2), 649\u2013672 (2007)","journal-title":"J. of Symbolic Logic"},{"issue":"3","key":"3_CR24","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: The Complexity of the Parity Argument and Other Inefficient proofs of Existence. J. of Computer and System Sciences\u00a048(3), 498\u2013532 (1994)","journal-title":"J. of Computer and System Sciences"},{"key":"3_CR25","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/S0049-237X(98)80023-2","volume-title":"Handbook of Proof Theory","author":"P. Pudl\u00e1k","year":"1998","unstructured":"Pudl\u00e1k, P.: The lengths of proofs. In: Buss, S.R. (ed.) Handbook of Proof Theory, pp. 547\u2013637. Elsevier, Amsterdam (1998)"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Pudl\u00e1k, P.: Consistency and games - in search of new combinatorial principles. In: Stoltenberg-Hansen, V., Vaananen, J. (eds.) Proc. Logic Colloquium 2003, Helsinki. Assoc. for Symbolic Logic, pp. 244\u2013281 (2006)","DOI":"10.1017\/9781316755785.014"},{"issue":"4","key":"3_CR27","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.2178\/jsl\/1230396927","volume":"73","author":"P. Pudl\u00e1k","year":"2008","unstructured":"Pudl\u00e1k, P.: Fragments of Bounded Arithmetic and the lengths of proofs. J. of Symbolic Logic\u00a073(4), 1389\u20131406 (2008)","journal-title":"J. of Symbolic Logic"},{"key":"3_CR28","unstructured":"Skelley, A., Thapen, N.: The provably total search problems of bounded arithmetic (preprint 2007) (revised March 2010)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15205-4_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:02:31Z","timestamp":1606186951000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15205-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642152047","9783642152054"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15205-4_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}