{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T22:18:21Z","timestamp":1784240301280,"version":"3.55.0"},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":8958,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1989,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the problem about the length of proofs of the sentences <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200041748_inline1\"\/> saying that there is no proof of contradiction in <jats:italic>S<\/jats:italic> whose length is <jats:italic>&lt; n<\/jats:italic>. We show the relation of this problem to some problems about propositional proof systems.<\/jats:p>","DOI":"10.2307\/2274765","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:31:33Z","timestamp":1146940293000},"page":"1063-1079","source":"Crossref","is-referenced-by-count":118,"title":["Propositional proof systems, the consistency of first order theories and the complexity of computations"],"prefix":"10.1017","volume":"54","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pavel","family":"Pudl\u00e1k","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200041748_ref013","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/065\/891256"},{"key":"S0022481200041748_ref011","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0168-0072(87)90066-2","article-title":"On the scheme of induction for bounded arithmetic formulas","volume":"35","author":"Paris","year":"1987","journal-title":"Annals of Pure and Applied Logic"},{"key":"S0022481200041748_ref008","volume-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik","author":"Kraj\u00ed\u02c7cek"},{"key":"S0022481200041748_ref005","unstructured":"Dowd M. , Model-theoretic aspects of preprint, 1985."},{"key":"S0022481200041748_ref001","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"S0022481200041748_ref006","volume-title":"On the consistency, completeness and correctness problems","author":"Friedman","year":"1979"},{"key":"S0022481200041748_ref003","first-page":"83","volume-title":"Proceedings of the seventh annual ACM symposium on the theory of computing","author":"Cook","year":"1975"},{"key":"S0022481200041748_ref014","volume-title":"The complexity of computing","author":"Savage","year":"1976"},{"key":"S0022481200041748_ref010","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0075316"},{"key":"S0022481200041748_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"S0022481200041748_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70462-2"},{"key":"S0022481200041748_ref009","first-page":"115","article-title":"Universal sorting problems","volume":"9","author":"Levin","year":"1973","journal-title":"Problemy Pereda\u010di Informacii"},{"key":"S0022481200041748_ref004","first-page":"36","volume":"44","author":"Cook","year":"1979","journal-title":"The relative efficiency of propositional proof systems"},{"key":"S0022481200041748_ref002","volume-title":"Bounded arithmetic","author":"Buss","year":"1986"},{"key":"S0022481200041748_ref016","volume-title":"Relativization, readabilities and the exponential hierarchy","author":"Wilson","year":"1980"},{"key":"S0022481200041748_ref015","volume-title":"Subsystems of arithmetic and complexity theory","author":"Wilkie","year":"1987"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200041748","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T15:52:21Z","timestamp":1558281141000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200041748\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,9]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1989,9]]}},"alternative-id":["S0022481200041748"],"URL":"https:\/\/doi.org\/10.2307\/2274765","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,9]]}}}