{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,4]],"date-time":"2024-02-04T07:40:46Z","timestamp":1707032446060},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":5763,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1998,6]]},"abstract":"<jats:p>A Frege proof system<jats:italic>F<\/jats:italic>is any standard system of prepositional calculus, e.g., a Hilbert style system based on finitely many axiom schemes and inference rules. An Extended Frege system<jats:italic>EF<\/jats:italic>is obtained from<jats:italic>F<\/jats:italic>as follows. An<jats:italic>EF<\/jats:italic>-sequence is a sequence of formulas \u03c8<jats:sub>1<\/jats:sub>, \u2026, \u03c8<jats:sub>\u03ba<\/jats:sub>such that each\u03c8<jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>is either an axiom of<jats:italic>F<\/jats:italic>, inferred from previous \u03c8<jats:sub><jats:italic>u<\/jats:italic><\/jats:sub>and \u03c8<jats:sub><jats:italic>v<\/jats:italic><\/jats:sub>(= \u03c8<jats:sub><jats:italic>u<\/jats:italic><\/jats:sub>\u2192 \u03c8<jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>) by modus ponens or of the form<jats:italic>q<\/jats:italic>\u2194 \u03c6, where<jats:italic>q<\/jats:italic>is an atom occurring neither in \u03c6 nor in any of \u03c8<jats:sub>1<\/jats:sub>,\u2026,\u03c8<jats:sub><jats:italic>i<\/jats:italic>\u22121<\/jats:sub>. Such<jats:italic>q<\/jats:italic>\u2194 \u03c6, is called an extension axiom and<jats:italic>q<\/jats:italic>a new extension atom. An<jats:italic>EF<\/jats:italic>-proof is any<jats:italic>EF<\/jats:italic>-sequence whose last formula does not contain any extension atom. In [12], S. A. Cook and R. Reckhow proved that the pigeonhole principle<jats:italic>PHP<\/jats:italic>has a simple polynomial size<jats:italic>EF<\/jats:italic>-proof and conjectured that<jats:italic>PHP<\/jats:italic>does not admit polynomial size<jats:italic>F<\/jats:italic>-proof. In [5], S. R. Buss refuted this conjecture by furnishing polynomial size<jats:italic>F<\/jats:italic>-proof for<jats:italic>PHP<\/jats:italic>. Since then the important separation problem of polynomial size<jats:italic>F<\/jats:italic>and polynomial size<jats:italic>EF<\/jats:italic>has not shown any progress.<\/jats:p><jats:p>In [11], S. A. Cook introduced the system<jats:italic>PV<\/jats:italic>, a free variable equational logic whose provable functional equalities are \u2018polynomial time verifiable\u2019 and showed that the metamathematics of<jats:italic>F<\/jats:italic>and<jats:italic>EF<\/jats:italic>can be developed in<jats:italic>PV<\/jats:italic>and the soundness of<jats:italic>EF<\/jats:italic>proved in<jats:italic>PV<\/jats:italic>. In [3], S. R. Buss introduced the first order system<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200015176_inline1.png\" \/>and showed that<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200015176_inline1.png\" \/>is essentially a conservative extension of<jats:italic>PV<\/jats:italic>. There he also introduced a second order system<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200015176_inline2.png\" \/>(<jats:italic>BD<\/jats:italic>).<\/jats:p>","DOI":"10.2307\/2586859","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:01:17Z","timestamp":1146938477000},"page":"709-738","source":"Crossref","is-referenced-by-count":0,"title":["Frege proof system and TNC\u00b0"],"prefix":"10.1017","volume":"63","author":[{"given":"Gaisi","family":"Takeuti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200015176_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF01531023"},{"key":"S0022481200015176_ref023","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1093\/oso\/9780198536901.003.0016","volume-title":"Arithmetic, proof theory and computational complexity","author":"Takeuti","year":"1993"},{"key":"S0022481200015176_ref004","first-page":"123","volume-title":"Proceedings of the 19th annual ACM symposium on theory of computing","author":"Buss","year":"1987"},{"key":"S0022481200015176_ref015","first-page":"539","volume-title":"Proceedings of the 20th annual ACM symposium on theory of computation","author":"Karchmer","year":"1988"},{"key":"S0022481200015176_ref022","doi-asserted-by":"publisher","DOI":"10.1007\/BF01621092"},{"key":"S0022481200015176_ref016","unstructured":"Kraj\u00ed\u010dek, J. , Bounded arithmetic, propositional logic and complexity theory, Cambridge University Press, to appear."},{"key":"S0022481200015176_ref017","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_10"},{"key":"S0022481200015176_ref014","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/1948.001.0001"},{"key":"S0022481200015176_ref019","first-page":"287","volume-title":"Proceedings of the 22nd annual ACM symposium on theory of computing","author":"Raz","year":"1990"},{"key":"S0022481200015176_ref002","first-page":"95","volume-title":"In proof theory, complexity and arithmetic","author":"Buss"},{"key":"S0022481200015176_ref024","doi-asserted-by":"publisher","DOI":"10.1007\/BF02390458"},{"key":"S0022481200015176_ref001","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1988.5262"},{"key":"S0022481200015176_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90036-L"},{"key":"S0022481200015176_ref013","unstructured":"Dowd, M. , Propositional representation of arithmetical proofs, Ph.D. dissertation , University of Toronto, 04 1979, Department of Computer Science Technical Report 132\/79."},{"key":"S0022481200015176_ref012","first-page":"36","volume":"44","author":"Cook","year":"1977","journal-title":"The relative efficiency of propositional proof systems"},{"key":"S0022481200015176_ref007","doi-asserted-by":"publisher","DOI":"10.1137\/0221046"},{"key":"S0022481200015176_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-3466-1_4"},{"key":"S0022481200015176_ref020","first-page":"798","article-title":"Lower bounds on the monotone complexity of some Boolean functions","volume":"281","author":"Razborov","year":"1985","journal-title":"Doklady AkademiiNauk SSSR"},{"key":"S0022481200015176_ref003","volume-title":"Bounded arithmetic","author":"Buss","year":"1986"},{"key":"S0022481200015176_ref005","first-page":"66","volume":"52","author":"Buss","year":"1987","journal-title":"Polynomial size proofs of the propositional pigeonhole principle"},{"key":"S0022481200015176_ref011","first-page":"83","volume-title":"Proceedings of the 7th ACM symposium on the theory of computation","author":"Cook","year":"1975"},{"key":"S0022481200015176_ref018","first-page":"1063","volume":"54","author":"Kraj\u00ed\u010dek","year":"1989","journal-title":"Propositional proof systems, the consistency of first order theories and the complexity of computations"},{"key":"S0022481200015176_ref010","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_6"},{"key":"S0022481200015176_ref021","unstructured":"Reckhow, R. A. , On the lengths of proofs in the propositional calculus, Ph.D. thesis , University of Toronto, 1976, Department of Computer Science, Technical Report 87."}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200015176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,4]],"date-time":"2024-02-04T07:19:23Z","timestamp":1707031163000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200015176\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,6]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,6]]}},"alternative-id":["S0022481200015176"],"URL":"https:\/\/doi.org\/10.2307\/2586859","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,6]]}}}