{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:29:26Z","timestamp":1750307366555,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,7,1]],"date-time":"2010-07-01T00:00:00Z","timestamp":1277942400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KO 1053\/5-1KO 1053\/5-2"],"award-info":[{"award-number":["KO 1053\/5-1KO 1053\/5-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2010,7]]},"abstract":"<jats:p>\n            Cook and Kraj\u00ed\u010dek have recently obtained the following Karp-Lipton collapse result in bounded arithmetic: if the theory\n            <jats:italic>PV<\/jats:italic>\n            proves NP\u2286 P\/\n            <jats:italic>poly<\/jats:italic>\n            , then the polynomial hierarchy collapses to the Boolean hierarchy, and this collapse is provable in\n            <jats:italic>PV<\/jats:italic>\n            . Here we show the converse implication, thus answering an open question posed by Cook and Kraj\u00ed\u010dek. We obtain this result by formalizing in\n            <jats:italic>PV<\/jats:italic>\n            a hard\/easy argument of Buhrman et al. [2003].\n          <\/jats:p>\n          <jats:p>In addition, we continue the investigation of propositional proof systems using advice, initiated by Cook and Kraj\u00ed\u010dek. In particular, we obtain several optimality results for proof systems using advice. We further show that these optimal systems are equivalent to natural extensions of Frege systems.<\/jats:p>","DOI":"10.1145\/1805950.1805952","type":"journal-article","created":{"date-parts":[[2010,7,15]],"date-time":"2010-07-15T12:48:46Z","timestamp":1279198126000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A tight Karp-Lipton collapse result in bounded arithmetic"],"prefix":"10.1145","volume":"11","author":[{"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Leibniz-Universit\u00e4t Hannover, Hannover, Germany"}]},{"given":"Sebastian","family":"M\u00fcller","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2010,7,20]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Balc\u00e1zar J. L. D\u00edaz J. and Gabarr\u00f3 J. 1988. Structural Complexity I. Springer-Verlag Berlin.  Balc\u00e1zar J. L. D\u00edaz J. and Gabarr\u00f3 J. 1988. Structural Complexity I. Springer-Verlag Berlin.","key":"e_1_2_1_1_1","DOI":"10.1007\/978-3-642-97062-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1016\/0304-3975(91)90160-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1007\/978-3-642-00982-2_14"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science","volume":"2607","author":"Buhrman H.","unstructured":"Buhrman , H. , Chang , R. , and Fortnow , L . 2003. One bit of advice . In Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science , vol. 2607 . Springer-Verlag, Berlin, 547--558. Buhrman, H., Chang, R., and Fortnow, L. 2003. One bit of advice. In Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2607. Springer-Verlag, Berlin, 547--558."},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1016\/j.jcss.2003.07.015"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1016\/j.ic.2005.01.002"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1137\/S0097539790178069"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/800116.803756"},{"volume-title":"Complexity of Computations and Proofs","author":"Cook S. A.","unstructured":"Cook , S. A. 2005. Theories for complexity classes and their propositional translations . In Complexity of Computations and Proofs , J. Kraj\u00ed\u010dek, Ed. Quaderni di Matematica , 175--227. Cook, S. A. 2005. Theories for complexity classes and their propositional translations. In Complexity of Computations and Proofs, J. Kraj\u00ed\u010dek, Ed. Quaderni di Matematica, 175--227.","key":"e_1_2_1_9_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.2178\/jsl\/1203350791"},{"doi-asserted-by":"crossref","unstructured":"Cook S. A. and Nguyen P. 2010. Logical Foundations of Proof Complexity. Cambridge University Press.   Cook S. A. and Nguyen P. 2010. Logical Foundations of Proof Complexity. Cambridge University Press.","key":"e_1_2_1_11_1","DOI":"10.1017\/CBO9780511676277"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.2307\/2273702"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1109\/CCC.2005.15"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.2178\/jsl\/1245158087"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1137\/0217080"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/800141.804678"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1137\/S0097539795296206"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.5555\/225488"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.2307\/2274765"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1016\/0168-0072(91)90043-L"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1016\/S0304-3975(01)00155-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.2307\/2275794"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1805950.1805952","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1805950.1805952","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:42Z","timestamp":1750245762000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1805950.1805952"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["10.1145\/1805950.1805952"],"URL":"https:\/\/doi.org\/10.1145\/1805950.1805952","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2010,7]]},"assertion":[{"value":"2008-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}