{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T10:58:30Z","timestamp":1725533910199},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642027765"},{"type":"electronic","value":"9783642027772"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02777-2_8","type":"book-chapter","created":{"date-parts":[[2009,6,26]],"date-time":"2009-06-26T06:58:18Z","timestamp":1245999498000},"page":"65-72","source":"Crossref","is-referenced-by-count":2,"title":["Does Advice Help to Prove Propositional Tautologies?"],"prefix":"10.1007","author":[{"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"M\u00fcller","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0304-3975(92)90353-H","volume":"99","author":"J. Balc\u00e1zar","year":"1992","unstructured":"Balc\u00e1zar, J., Sch\u00f6ning, U.: Logarithmic advice classes. Theoretical Computer Science\u00a099, 279\u2013290 (1992)","journal-title":"Theoretical Computer Science"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-642-00982-2_14","volume-title":"Proc. 3rd International Conference on Language and Automata Theory and Applications","author":"O. Beyersdorff","year":"2009","unstructured":"Beyersdorff, O., K\u00f6bler, J., M\u00fcller, S.: Nondeterministic instance complexity and proof systems with advice. In: Proc. 3rd International Conference on Language and Automata Theory and Applications. LNCS, vol.\u00a05457, pp. 164\u2013175. Springer, Heidelberg (2009)"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/978-3-540-87531-4_16","volume-title":"Computer Science Logic","author":"O. Beyersdorff","year":"2008","unstructured":"Beyersdorff, O., M\u00fcller, S.: A tight Karp-Lipton collapse result in bounded arithmetic. In: Kaminski, M., Martini, S. (eds.) CSL 2008. LNCS, vol.\u00a05213, pp. 199\u2013214. Springer, Heidelberg (2008)"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Hitchcock, J.M.: NP-hard sets are exponentially dense unless coNP \u2286 NP\/poly. In: Proc. 23rd Annual IEEE Conference on Computational Complexity, pp. 1\u20137 (2008)","DOI":"10.1109\/CCC.2008.21"},{"issue":"4","key":"8_CR5","doi-asserted-by":"publisher","first-page":"1353","DOI":"10.2178\/jsl\/1203350791","volume":"72","author":"S.A. Cook","year":"2007","unstructured":"Cook, S.A., Kraj\u00ed\u010dek, J.: Consequences of the provability of NP \u2286 P\/poly. The Journal of Symbolic Logic\u00a072(4), 1353\u20131371 (2007)","journal-title":"The Journal of Symbolic Logic"},{"issue":"1","key":"8_CR6","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook, S.A., Reckhow, R.A.: The relative efficiency of propositional proof systems. The Journal of Symbolic Logic\u00a044(1), 36\u201350 (1979)","journal-title":"The Journal of Symbolic Logic"},{"issue":"1","key":"8_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0890-5401(03)00058-0","volume":"184","author":"J. K\u00f6bler","year":"2003","unstructured":"K\u00f6bler, J., Messner, J., Tor\u00e1n, J.: Optimal proof systems imply complete sets for promise classes. Information and Computation\u00a0184(1), 71\u201392 (2003)","journal-title":"Information and Computation"},{"issue":"3","key":"8_CR8","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.2307\/2274765","volume":"54","author":"J. Kraj\u00ed\u010dek","year":"1989","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P.: Propositional proof systems, the consistency of first order theories and the complexity of computations. The Journal of Symbolic Logic\u00a054(3), 1063\u20131079 (1989)","journal-title":"The Journal of Symbolic Logic"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02777-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T00:52:38Z","timestamp":1552092758000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02777-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642027765","9783642027772"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02777-2_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}