{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T19:04:29Z","timestamp":1784574269510,"version":"3.55.0"},"reference-count":9,"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":3571,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,6]]},"abstract":"<jats:title>Abstract.<\/jats:title><jats:p>We describe a general method how to construct from a prepositional proof system <jats:italic>P<\/jats:italic> a possibly much stronger proof system <jats:italic>iP<\/jats:italic>. The system <jats:italic>iP<\/jats:italic> operates with exponentially long <jats:italic>P<\/jats:italic>-proofs described \u201cimplicitly\u201d by polynomial size circuits.<\/jats:p><jats:p>As an example we prove that proof system <jats:italic>i<\/jats:italic>EF, <jats:italic>implicit<\/jats:italic> EF, corresponds to bounded arithmetic theory <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007799_inline1\"\/> and hence, in particular, polynomially simulates the quantified prepositional calculus <jats:italic>G<\/jats:italic> and the <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007799_inline2\"\/>-consequences of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007799_inline3\"\/> proved with one use of exponentiation. Furthermore, the soundness of <jats:italic>i<\/jats:italic>EF is not provable in <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007799_inline3\"\/>. An iteration of the construction yields a proof system corresponding to <jats:italic>T<\/jats:italic><jats:sup>2<\/jats:sup> + <jats:italic>Exp<\/jats:italic> and, in principle, to much stronger theories.<\/jats:p>","DOI":"10.2178\/jsl\/1082418532","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T16:34:17Z","timestamp":1109781257000},"page":"387-397","source":"Crossref","is-referenced-by-count":15,"title":["Implicit proofs"],"prefix":"10.1017","volume":"69","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007799_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-3466-1_15"},{"key":"S0022481200007799_ref006","volume-title":"Diagonalization in proof complexity","author":"Kraj\u00ed\u010dek","year":"2003"},{"key":"S0022481200007799_ref001","volume-title":"Bounded arithmetic","author":"Buss","year":"1986"},{"key":"S0022481200007799_ref007","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":"S0022481200007799_ref003","first-page":"36","volume":"44","author":"Cook","year":"1979","journal-title":"The relative efficiency of propositional proof systems"},{"key":"S0022481200007799_ref005","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"},{"key":"S0022481200007799_ref002","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803756"},{"key":"S0022481200007799_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90023-U"},{"key":"S0022481200007799_ref008","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19900360106"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T17:02:52Z","timestamp":1557162172000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007799\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,6]]}},"alternative-id":["S0022481200007799"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1082418532","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,6]]}}}