{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T05:14:37Z","timestamp":1740028477252,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240587"},{"type":"electronic","value":"9783540305385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30538-5_11","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:40:30Z","timestamp":1268401230000},"page":"122-134","source":"Crossref","is-referenced-by-count":2,"title":["Representable Disjoint NP-Pairs"],"prefix":"10.1007","author":[{"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S. Cook","year":"1979","unstructured":"Cook, S., Reckhow, R.: The relative efficiency of propositional proof systems. Journal of Symbolic Logic\u00a044, 36\u201350 (1979)","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Gla\u00dfer, C., Selman, A., Sengupta, S., Zhang, L.: Disjoint NP-pairs. In: Proceedings 18th Annual IEEE Conference on Computational Complexity, pp. 313\u2013332 (2003)","DOI":"10.1109\/CCC.2003.1214430"},{"key":"11_CR3","unstructured":"Gla\u00dfer, C., Selman, A., Sengupta, S.: Reductions between disjoint NP-pairs. In: Proceedings 19th Annual IEEE Conference on Computational Complexity (2004)"},{"issue":"2","key":"11_CR4","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"Grollmann, J., Selman, A.: Complexity measures for public-key cryptosystems. SIAM Journal on Computing\u00a017(2), 309\u2013335 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"11_CR5","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, 71\u201392 (2003)","journal-title":"Information and Computation"},{"key":"11_CR6","volume-title":"Encyclopedia of Mathematics and Its Applications","author":"J. Kraj\u00ed\u010dek","year":"1995","unstructured":"Kraj\u00ed\u010dek, J.: Bounded Arithmetic, Propositional Logic, and Complexity Theory. In: Encyclopedia of Mathematics and Its Applications, vol.\u00a060. Cambridge University Press, Cambridge (1995)"},{"issue":"2","key":"11_CR7","doi-asserted-by":"publisher","first-page":"387","DOI":"10.2178\/jsl\/1082418532","volume":"69","author":"J. Kraj\u00ed\u010dek","year":"2004","unstructured":"Kraj\u00ed\u010dek, J.: Implicit proofs. Journal of Symbolic Logic\u00a069(2), 387\u2013397 (2004)","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1002\/malq.19900360106","volume":"36","author":"J. Kraj\u00ed\u010dek","year":"1990","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P.: Quantified propositional calculi and fragments of bounded arithmetic. Zeitschr.\u00a0f.\u00a0math.\u00a0Logik und Grundlagen d.\u00a0Math.\u00a036, 29\u201346 (1990)","journal-title":"Zeitschr.\u00a0f.\u00a0math.\u00a0Logik und Grundlagen d.\u00a0Math."},{"issue":"1","key":"11_CR9","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":"11_CR10","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/S0049-237X(98)80023-2","volume-title":"Handbook of Proof Theory","author":"P. Pudl\u00e1k","year":"1998","unstructured":"Pudl\u00e1k, P.: The lengths of proofs. In: Buss, S.R. (ed.) Handbook of Proof Theory, pp. 547\u2013637. Elsevier, Amsterdam (1998)"},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/3-540-44683-4_54","volume-title":"Mathematical Foundations of Computer Science 2001","author":"P. Pudl\u00e1k","year":"2001","unstructured":"Pudl\u00e1k, P.: On reducibility and symmetry of disjoint NP-pairs. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 621\u2013632. Springer, Heidelberg (2001)"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Razborov, A.A.: On provably disjoint NP-pairs. Technical Report TR94-006, Electronic Colloquium on Computational Complexity (1994)","DOI":"10.7146\/brics.v1i36.21607"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30538-5_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T12:11:33Z","timestamp":1739967093000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30538-5_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240587","9783540305385"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30538-5_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}