{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:35:48Z","timestamp":1725536148592},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642033506"},{"type":"electronic","value":"9783642033513"}],"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-03351-3_7","type":"book-chapter","created":{"date-parts":[[2009,8,3]],"date-time":"2009-08-03T12:53:58Z","timestamp":1249304038000},"page":"47-58","source":"Crossref","is-referenced-by-count":6,"title":["Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes"],"prefix":"10.1007","author":[{"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[]},{"given":"Zenon","family":"Sadowski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I","author":"J.L. Balc\u00e1zar","year":"1988","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, J.: Structural Complexity I. Springer, Heidelberg (1988)"},{"issue":"1-3","key":"7_CR2","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.tcs.2007.02.005","volume":"377","author":"O. Beyersdorff","year":"2007","unstructured":"Beyersdorff, O.: Classes of representable disjoint NP-pairs. Theoretical Computer Science\u00a0377(1-3), 93\u2013109 (2007)","journal-title":"Theoretical Computer Science"},{"key":"7_CR3","unstructured":"Beyersdorff, O., K\u00f6bler, J., Messner, J.: Nondeterministic functions and the existence of optimal proof systems. Theoretical Computer Science (in press)"},{"key":"7_CR4","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":"7_CR5","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: Feasibly constructive proofs and the propositional calculus. In: Proc. 7th Annual ACM Symposium on Theory of Computing, pp. 83\u201397 (1975)","DOI":"10.1145\/800116.803756"},{"issue":"4","key":"7_CR6","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":"7_CR7","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":"2","key":"7_CR8","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.ic.2005.03.003","volume":"200","author":"C. Gla\u00dfer","year":"2005","unstructured":"Gla\u00dfer, C., Selman, A.L., Sengupta, S.: Reductions between disjoint NP-pairs. Information and Computation\u00a0200(2), 247\u2013267 (2005)","journal-title":"Information and Computation"},{"issue":"6","key":"7_CR9","doi-asserted-by":"publisher","first-page":"1369","DOI":"10.1137\/S0097539703425848","volume":"33","author":"C. Gla\u00dfer","year":"2004","unstructured":"Gla\u00dfer, C., Selman, A.L., Sengupta, S., Zhang, L.: Disjoint NP-pairs. SIAM Journal on Computing\u00a033(6), 1369\u20131416 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/11685654_11","volume-title":"Essays in Theoretical Computer Science in Memory of Shimon Even","author":"C. Gla\u00dfer","year":"2006","unstructured":"Gla\u00dfer, C., Selman, A.L., Zhang, L.: Survey of disjoint NP-pairs and relations to propositional proof systems. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Essays in Theoretical Computer Science in Memory of Shimon Even, pp. 241\u2013253. Springer, Heidelberg (2006)"},{"issue":"1-3","key":"7_CR11","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2006.10.006","volume":"370","author":"C. Gla\u00dfer","year":"2007","unstructured":"Gla\u00dfer, C., Selman, A.L., Zhang, L.: Canonical disjoint NP-pairs of propositional proof systems. Theoretical Computer Science\u00a0370(1-3), 60\u201373 (2007)","journal-title":"Theoretical Computer Science"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0304-3975(88)90022-9","volume":"58","author":"J. Hartmanis","year":"1988","unstructured":"Hartmanis, J., Hemachandra, L.A.: Complexity classes without machines: On complete languages for UP. Theoretical Computer Science\u00a058, 129\u2013142 (1988)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"7_CR13","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"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/BFb0030318","volume-title":"Mathematical Foundations of Computer Science 1984","author":"W. Kowalczyk","year":"1984","unstructured":"Kowalczyk, W.: Some connections between representability of complexity classes and the power of formal systems of reasoning. In: Chytil, M.P., Koubek, V. (eds.) MFCS 1984. LNCS, vol.\u00a0176, pp. 364\u2013369. Springer, Heidelberg (1984)"},{"issue":"3","key":"7_CR15","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"},{"issue":"1","key":"7_CR16","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1006\/inco.1997.2674","volume":"140","author":"J. Kraj\u00ed\u010dek","year":"1998","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P.: Some consequences of cryptographical conjectures for $S^1_2$ and EF. Information and Computation\u00a0140(1), 82\u201394 (1998)","journal-title":"Information and Computation"},{"key":"7_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/BFb0036203","volume-title":"Fundamentals of Computation Theory","author":"Z. Sadowski","year":"1997","unstructured":"Sadowski, Z.: On an optimal quantified propositional proof system and a complete language for NP \u2229 co-NP. In: Chlebus, B.S., Czaja, L. (eds.) FCT 1997. LNCS, vol.\u00a01279, pp. 423\u2013428. Springer, Heidelberg (1997)"},{"issue":"1","key":"7_CR18","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0304-3975(01)00155-4","volume":"288","author":"Z. Sadowski","year":"2002","unstructured":"Sadowski, Z.: On an optimal propositional proof system and the structure of easy subsets of TAUT. Theoretical Computer Science\u00a0288(1), 181\u2013193 (2002)","journal-title":"Theoretical Computer Science"},{"key":"7_CR19","unstructured":"Sadowski, Z.: Optimal proof systems and complete languages. In: Local Proc. 4th Conference on Computability in Europe, pp. 407\u2013414. University of Athens (2008)"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Selman, A.L.: Much ado about functions. In: Proc. 11th Annual IEEE Conference on Computational Complexity, pp. 198\u2013212 (1996)","DOI":"10.1109\/CCC.1996.507682"}],"container-title":["Lecture Notes in Computer Science","Computer Science - Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03351-3_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T20:40:27Z","timestamp":1558471227000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03351-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642033506","9783642033513"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03351-3_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}