{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T22:10:03Z","timestamp":1740521403149,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228493"},{"type":"electronic","value":"9783540278368"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_4","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T22:53:21Z","timestamp":1284591201000},"page":"8-14","source":"Crossref","is-referenced-by-count":0,"title":["Feasible Proofs and Computations: Partnership and Fusion"],"prefix":"10.1007","author":[{"given":"Alexander A.","family":"Razborov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Ben-Sasson, E., Razborov, A., Wigderson, A.: Pseudorandom generators in propositional complexity. In: Proceedings of the 41st IEEE FOCS, pp. 43\u201353 (2000); Journal version to appear in SIAM Journal on Computing","DOI":"10.1109\/SFCS.2000.892064"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.: Resolution is not automatizable unless W[P] is tractable. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 210\u2013219 (2001)","DOI":"10.1109\/SFCS.2001.959895"},{"key":"4_CR3","first-page":"18","volume":"242","author":"M. Alekhnovich","year":"2003","unstructured":"Alekhnovich, M., Razborov, A.: Lower bounds for the polynomial calculus: non-binomial case. Proceedings of the Steklov Institute of Mathematics\u00a0242, 18\u201335 (2003)","journal-title":"Proceedings of the Steklov Institute of Mathematics"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S.: The approximability of NP-hard problems. In: Proceedings of the 30th ACM Symposium on the Theory of Computing, pp. 337\u2013348 (1998)","DOI":"10.1145\/276698.276784"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and intractability of approximation problems. In: Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 13\u201322 (1992)","DOI":"10.1109\/SFCS.1992.267823"},{"issue":"1","key":"4_CR6","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, M.: Probabilistic checking of proofs: a new characterization of np. Journal of the ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"Journal of the ACM"},{"key":"4_CR7","series-title":"Combinatorial optimization problems and their approximability properties","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Combinatorial optimization problems and their approximability properties. Springer, Heidelberg (1999)"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Babai, L.: Trading group theory for randomness. In: Proceedings of the 17th ACMSymposium on the Theory of Computing, pp. 421\u2013429 (1985)","DOI":"10.1145\/22145.22192"},{"key":"4_CR9","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/978-3-0348-9110-3_2","volume-title":"Proceedings of the First European Congress of Mathematics","author":"L. Babai","year":"1994","unstructured":"Babai, L.: Transparent proofs and limits to approximations. In: Proceedings of the First European Congress of Mathematics, vol.\u00a0I, pp. 31\u201391. Birkh\u00e4user, Basel (1994)"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Lund, C., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the 23rd ACM Symposium on the Theory of Computing, pp. 21\u201331 (1991)","DOI":"10.1145\/103418.103428"},{"key":"4_CR11","unstructured":"Beame, P., Pitassi, T.: Propositional proof complexity: Past, present and future. Technical Report TR98-067, Electronic Colloquium on Computational Complexity (1998), Available at ftp:\/\/ftp.eccc.uni-trier.de\/pub\/eccc\/reports\/1998\/TR98-067\/index.html"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Bonet, M., Domingo, C., Gavald\u00e1, R., Maciel, A., Pitassi, T.: Non-automatizability of bounded-depth Frege proofs. In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, pp. 15\u201323 (1999)","DOI":"10.1109\/CCC.1999.766258"},{"issue":"3","key":"4_CR13","doi-asserted-by":"publisher","first-page":"708","DOI":"10.2307\/2275569","volume":"62","author":"M. Bonet","year":"1997","unstructured":"Bonet, M., Pitassi, T., Raz, R.: Lower bounds for cutting planes proofs with small coefficients. Journal of Symbolic Logic\u00a062(3), 708\u2013728 (1997)","journal-title":"Journal of Symbolic Logic"},{"issue":"6","key":"4_CR14","doi-asserted-by":"publisher","first-page":"1939","DOI":"10.1137\/S0097539798353230","volume":"29","author":"M. Bonet","year":"2000","unstructured":"Bonet, M., Pitassi, T., Raz, R.: On interpolation and automatization for Frege systems. SIAM Journal on Computing\u00a029(6), 1939\u20131967 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR15","unstructured":"Buss, S.R.: Bounded Arithmetic. Bibliopolis, Napoli (1986)"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"issue":"1","key":"4_CR17","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook, S.A., Reckhow, A.R.: The relative efficiency of propositional proof systems. Journal of Symbolic Logic\u00a044(1), 36\u201350 (1979)","journal-title":"Journal of Symbolic Logic"},{"issue":"2","key":"4_CR18","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. Journal of the ACM\u00a043(2), 268\u2013292 (1996)","journal-title":"Journal of the ACM"},{"key":"4_CR19","doi-asserted-by":"crossref","first-page":"1395","DOI":"10.1007\/978-3-0348-9078-6_134","volume-title":"Proceedings of the International Congress of Mathematicians (Zurich, 1994)","author":"O. Goldreich","year":"1995","unstructured":"Goldreich, O.: Probabilistic proof systems. In: Proceedings of the International Congress of Mathematicians (Zurich, 1994), pp. 1395\u20131406. Birkh\u00e4user, Basel (1995)"},{"key":"4_CR20","volume-title":"Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Algorithms and Combinatorics","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O.: Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Algorithms and Combinatorics, vol.\u00a017. Springer, Heidelberg (1998)"},{"issue":"1","key":"4_CR21","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1985","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing\u00a018(1), 186\u2013208 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR22","unstructured":"Goldwasser, S., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity, and a methodology of cryptographic protocol design. In: Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 39\u201348 (1986)"},{"key":"4_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-22156-3","volume-title":"Metamathematics of First-Order Arithmetic","author":"P. H\u00e1jek","year":"1993","unstructured":"H\u00e1jek, P., Pudl\u00e1k, P.: Metamathematics of First-Order Arithmetic. Springer, Heidelberg (1993)"},{"issue":"1","key":"4_CR24","doi-asserted-by":"publisher","first-page":"73","DOI":"10.2307\/2275250","volume":"59","author":"J. Kraj\u00ed\u010dek","year":"1994","unstructured":"Kraj\u00ed\u010dek, J.: Lower bounds to the size of constant-depth propositional proofs. Journal of Symbolic Logic\u00a059(1), 73\u201386 (1994)","journal-title":"Journal of Symbolic Logic"},{"key":"4_CR25","doi-asserted-by":"publisher","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. Cambridge University Press, Cambridge (1995)"},{"issue":"2","key":"4_CR26","doi-asserted-by":"publisher","first-page":"457","DOI":"10.2307\/2275541","volume":"62","author":"J. Kraj\u00ed\u010dek","year":"1997","unstructured":"Kraj\u00ed\u010dek, J.: Interpolation theorems, lower bounds for proof systems and independence results for bounded arithmetic. Journal of Symbolic Logic\u00a062(2), 457\u2013486 (1997)","journal-title":"Journal of Symbolic Logic"},{"issue":"1-3","key":"4_CR27","doi-asserted-by":"publisher","first-page":"123","DOI":"10.4064\/fm170-1-8","volume":"170","author":"J.. Kraj\u00ed\u010dek","year":"2001","unstructured":"Kraj\u00ed\u010dek, J.: On the weak pigeonhole principle. Fundamenta Mathematicae\u00a0170(1-3), 123\u2013140 (2001)","journal-title":"Fundamenta Mathematicae"},{"issue":"1","key":"4_CR28","doi-asserted-by":"publisher","first-page":"265","DOI":"10.2178\/jsl\/1080938841","volume":"69","author":"J.. Kraj\u00ed\u010dek","year":"2004","unstructured":"Kraj\u00ed\u010dek, J.: Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds. Journal of Symbolic Logic\u00a069(1), 265\u2013286 (2004)","journal-title":"Journal of Symbolic Logic"},{"key":"4_CR29","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1006\/inco.1997.2674","volume":"142","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\u00a0142, 82\u201394 (1998)","journal-title":"Information and Computation"},{"issue":"4","key":"4_CR30","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. Journal of the ACM\u00a039(4), 859\u2013868 (1992)","journal-title":"Journal of the ACM"},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"494","DOI":"10.2307\/2269958","volume":"36","author":"R.J. Parikh","year":"1971","unstructured":"Parikh, R.J.: Existence and feasibility in arithmetic. Journal of Symbolic Logic\u00a036, 494\u2013508 (1971)","journal-title":"Journal of Symbolic Logic"},{"key":"4_CR32","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/BFb0075316","volume-title":"Methods in Mathematical Logic","author":"J. Paris","year":"1985","unstructured":"Paris, J., Wilkie, A.: Counting problems in bounded arithmetic. In: Methods in Mathematical Logic. Lecture Notes in Mathematics, vol.\u00a01130, pp. 317\u2013340. Springer, Heidelberg (1985)"},{"issue":"3","key":"4_CR33","doi-asserted-by":"publisher","first-page":"981","DOI":"10.2307\/2275583","volume":"62","author":"P. Pudl\u00e1k","year":"1997","unstructured":"Pudl\u00e1k, P.: Lower bounds for resolution and cutting planes proofs and monotone computations. Journal of Symbolic Logic\u00a062(3), 981\u2013998 (1997)","journal-title":"Journal of Symbolic Logic"},{"key":"4_CR34","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. (ed.) Handbook of Proof Theory, pp. 547\u2013637. Elsevier, Amsterdam (1998)"},{"issue":"2","key":"4_CR35","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/972639.972640","volume":"51","author":"R. Raz","year":"2004","unstructured":"Raz, R.: Resolution lower bounds for the weak pigeonhole principle. Journal of the ACM\u00a051(2), 115\u2013138 (2004)","journal-title":"Journal of the ACM"},{"key":"4_CR36","doi-asserted-by":"crossref","unstructured":"Razborov, A.: Bounded Arithmetic and lower bounds in Boolean complexity. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II. Progress in Computer Science and Applied Logic, vol.\u00a013, pp. 344\u2013386. Birkha\u00fcser (1995)","DOI":"10.1007\/978-1-4612-2566-9_12"},{"issue":"1","key":"4_CR37","first-page":"201","volume":"59","author":"A. Razborov","year":"1995","unstructured":"Razborov, A.: Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic. Izvestiya of the RAN\u00a059(1), 201\u2013224 (1995)","journal-title":"Izvestiya of the RAN"},{"key":"4_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/3-540-61440-0_116","volume-title":"Automata, Languages and Programming","author":"A. Razborov","year":"1996","unstructured":"Razborov, A.: Lower bounds for propositional proofs and independence results in Bounded Arithmetic. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol.\u00a01099, pp. 48\u201362. Springer, Heidelberg (1996)"},{"key":"4_CR39","unstructured":"Razborov, A.: Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution (2002), Manuscript available at http:\/\/www.genesis.mi.ras.ru\/~razborov"},{"key":"4_CR40","doi-asserted-by":"crossref","unstructured":"Razborov, A.: Resolution lower bounds for perfect matching principles. In: Proceedings of the 17th IEEE Conference on Computational Complexity, pp. 29\u201338 (2002)","DOI":"10.1109\/CCC.2002.1004336"},{"issue":"1","key":"4_CR41","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A. Razborov","year":"1997","unstructured":"Razborov, A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences\u00a055(1), 24\u201335 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR42","doi-asserted-by":"crossref","unstructured":"Regan, K., Sivakumar, D., Cai, J.: Pseudorandom generators, measure theory, and natural proofs. In: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, pp. 26\u201335 (1995)","DOI":"10.1109\/SFCS.1995.492459"},{"key":"4_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/3-540-63248-4_8","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"S. Rudich","year":"1997","unstructured":"Rudich, S.: Super-bits, demi-bits, and NP\/qpoly-natural proofs. In: Rolim, J.D.P. (ed.) RANDOM 1997. LNCS, vol.\u00a01269, pp. 85\u201393. Springer, Heidelberg (1997)"},{"issue":"4","key":"4_CR44","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP = PSPACE. Journal of the ACM\u00a039(4), 869\u2013877 (1992)","journal-title":"Journal of the ACM"},{"key":"4_CR45","unstructured":"Tseitin, G.C.: On the complexity of derivations in propositional calculus. In: Studies in constructive mathematics and mathematical logic, Part II. Consultants Bureau, New-York- London (1968)"},{"key":"4_CR46","doi-asserted-by":"publisher","first-page":"425","DOI":"10.2178\/bsl\/1203350879","volume":"1","author":"A. Urquhart","year":"1995","unstructured":"Urquhart, A.: The complexity of propositional proofs. Bulletin of Symbolic Logic\u00a01, 425\u2013467 (1995)","journal-title":"Bulletin of Symbolic Logic"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T21:31:05Z","timestamp":1740519065000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}