{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:18:43Z","timestamp":1781259523322,"version":"3.54.1"},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2293,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We prove the following results: (i) <jats:italic><jats:bold>PV<\/jats:bold><\/jats:italic> proves <jats:italic><jats:bold>NP<\/jats:bold><\/jats:italic> \u2286 <jats:bold><jats:italic>P<\/jats:italic>\/poly iff PV<\/jats:bold> proves <jats:italic><jats:bold>coNP<\/jats:bold><\/jats:italic> \u2286 <jats:italic><jats:bold>NP<\/jats:bold><\/jats:italic>\/<jats:italic>O<\/jats:italic>(1). (ii) If <jats:italic><jats:bold>PV<\/jats:bold><\/jats:italic> proves <jats:italic><jats:bold>NP<\/jats:bold><\/jats:italic> \u2286 <jats:italic><jats:bold>P\/poly<\/jats:bold><\/jats:italic> then <jats:italic><jats:bold>PV<\/jats:bold><\/jats:italic> proves that the Polynomial Hierarchy collapses to the Boolean Hierarchy, (iii) <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004965_inline1\"\/> proves <jats:italic><jats:bold>NP<\/jats:bold><\/jats:italic> \u2286 <jats:bold><jats:italic>P\/poly iff<\/jats:italic><\/jats:bold><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004965_inline1\"\/> proves <jats:italic><jats:bold>coNP<\/jats:bold><\/jats:italic> \u2286 <jats:italic><jats:bold>NP\/O<\/jats:bold><\/jats:italic>(log <jats:italic>n<\/jats:italic>). (iv) If <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004965_inline1\"\/> proves <jats:italic><jats:bold>NP<\/jats:bold><\/jats:italic> \u2286 <jats:italic><jats:bold>P\/poly<\/jats:bold><\/jats:italic> then <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004965_inline1\"\/> proves that the Polynomial Hierarchy collapses to <jats:italic><jats:bold>P<jats:sup>NP<\/jats:sup><\/jats:bold><\/jats:italic>[log <jats:italic>n<\/jats:italic>]. (v) If <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004965_inline2\"\/> proves <jats:italic><jats:bold>NP<\/jats:bold><\/jats:italic> \u2286 <jats:italic><jats:bold>P\/poly<\/jats:bold><\/jats:italic> then <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004965_inline2\"\/> proves that the Polynomial Hierarchy collapses to <jats:italic><jats:bold>P<jats:sup>NP<\/jats:sup><\/jats:bold><\/jats:italic>.<\/jats:p><jats:p>Motivated by these results we introduce a new concept in proof complexity: proof systems with advice, and we make some initial observations about them.<\/jats:p>","DOI":"10.2178\/jsl\/1203350791","type":"journal-article","created":{"date-parts":[[2008,3,25]],"date-time":"2008-03-25T14:42:11Z","timestamp":1206456131000},"page":"1353-1371","source":"Crossref","is-referenced-by-count":34,"title":["Consequences of the provability of <i>NP<\/i> \u2286 <i>P<\/i>\/<i>poly<\/i>"],"prefix":"10.1017","volume":"72","author":[{"given":"Stephen","family":"Cook","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200004965_ref019","first-page":"942","volume":"61","author":"Zambella","year":"1996","journal-title":"Notes on polynomially bounded arithmetic"},{"key":"S0022481200004965_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(99)00008-1"},{"key":"S0022481200004965_ref016","volume-title":"Bounded Arithmetic, Propositional Logic and Computational Complexity","author":"Kraj\u00ed\u010dek","year":"1995"},{"key":"S0022481200004965_ref015","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1993-1124169-X"},{"key":"S0022481200004965_ref014","first-page":"255","article-title":"Turing machines that take advice","volume":"30","author":"Karp","year":"1982","journal-title":"Enseignement Mathematique"},{"key":"S0022481200004965_ref010","first-page":"175","volume-title":"Complexity of Computations and Proofs","author":"Cook","year":"2005"},{"key":"S0022481200004965_ref008","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1109\/SFCS.2001.959938","volume-title":"\u2286 ZPPNP, Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Cai","year":"2001"},{"key":"S0022481200004965_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90075-D"},{"key":"S0022481200004965_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(98)80017-7"},{"key":"S0022481200004965_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00057-A"},{"key":"S0022481200004965_ref002","volume-title":"Bounded Arithmetic","author":"Buss","year":"1986"},{"key":"S0022481200004965_ref003","first-page":"57","volume-title":"Logic and Computation, Proceedings of a Workshop held at Carnegie Mellon University","volume":"106","author":"Buss","year":"1990"},{"key":"S0022481200004965_ref017","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90043-L"},{"key":"S0022481200004965_ref007","first-page":"116","volume-title":"Arithmetic, Proof Theory and Computational Complexity","author":"Buss","year":"1993"},{"key":"S0022481200004965_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90160-4"},{"key":"S0022481200004965_ref012","doi-asserted-by":"publisher","DOI":"10.1145\/1183278.1183283"},{"key":"S0022481200004965_ref011","unstructured":"Cook Stephen and Nguyen Phuong , Foundations of proof complexity: Bounded arithmetic and propositional translations, unpublished manuscript http:\/\/www.cs.toronto.edu\/~sacook\/, 2006."},{"key":"S0022481200004965_ref009","first-page":"83","volume-title":"Proceedings of the ACM Symposium on Theory Of Computing (STOC)","author":"Cook","year":"1975"},{"key":"S0022481200004965_ref013","first-page":"302","volume-title":"Proceedings of the ACM Symposium on Theory Of Computing (STOC)","author":"Karp","year":"1980"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200004965","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T15:42:51Z","timestamp":1556725371000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200004965\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["S0022481200004965"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1203350791","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12]]}}}