{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T10:17:21Z","timestamp":1648894641643},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,6,29]],"date-time":"2007-06-29T00:00:00Z","timestamp":1183075200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,8]]},"DOI":"10.1007\/s00224-007-9023-8","type":"journal-article","created":{"date-parts":[[2007,6,28]],"date-time":"2007-06-28T18:52:16Z","timestamp":1183056736000},"page":"118-135","source":"Crossref","is-referenced-by-count":5,"title":["Tuples of Disjoint $\\mathsf{NP}$ -Sets"],"prefix":"10.1007","volume":"43","author":[{"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,6,29]]},"reference":[{"key":"9023_CR1","doi-asserted-by":"crossref","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 $\\mathsf{NP}$ -pairs. Theor. Comput. Sci. 377, 93\u2013109 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9023_CR2","volume-title":"Bounded Arithmetic","author":"S.R. Buss","year":"1986","unstructured":"Buss, S.R.: Bounded Arithmetic. Bibliopolis, Napoli (1986)"},{"key":"9023_CR3","doi-asserted-by":"crossref","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. J. Symb. Log. 44, 36\u201350 (1979)","journal-title":"J. Symb. Log."},{"issue":"6","key":"9023_CR4","doi-asserted-by":"crossref","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 J. Comput. 33(6), 1369\u20131416 (2004)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9023_CR5","doi-asserted-by":"crossref","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 $\\mathsf{NP}$ -pairs. Inf. Comput. 200(2), 247\u2013267 (2005)","journal-title":"Inf. Comput."},{"key":"9023_CR6","doi-asserted-by":"crossref","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 $\\mathsf{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, Berlin (2006)"},{"issue":"2","key":"9023_CR7","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"Grollmann, J., Selman, A.L.: Complexity measures for public-key cryptosystems. SIAM J. Comput. 17(2), 309\u2013335 (1988)","journal-title":"SIAM J. Comput."},{"key":"9023_CR8","doi-asserted-by":"crossref","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. Inf. Comput. 184, 71\u201392 (2003)","journal-title":"Inf. Comput."},{"key":"9023_CR9","series-title":"Encyclopedia of Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511529948","volume-title":"Bounded Arithmetic, Propositional Logic, and Complexity Theory","author":"J. Kraj\u00ed\u010dek","year":"1995","unstructured":"Kraj\u00ed\u010dek, J.: Bounded Arithmetic, Propositional Logic, and Complexity Theory. Encyclopedia of Mathematics and Its Applications, vol.\u00a060. Cambridge University Press, Cambridge (1995)"},{"issue":"2","key":"9023_CR10","doi-asserted-by":"crossref","first-page":"457","DOI":"10.2307\/2275541","volume":"62","author":"J. Kraj\u00ed\u010dek","year":"1997","unstructured":"Kraj\u00ed\u010dek, J.: Interpolation theorems, lower bounds for proof systems and independence results for bounded arithmetic. J. Symb. Log. 62(2), 457\u2013486 (1997)","journal-title":"J. Symb. Log."},{"issue":"1","key":"9023_CR11","doi-asserted-by":"crossref","first-page":"265","DOI":"10.2178\/jsl\/1080938841","volume":"69","author":"J. Kraj\u00ed\u010dek","year":"2004","unstructured":"Kraj\u00ed\u010dek, J.: Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds. J. Symb. Log. 69(1), 265\u2013286 (2004)","journal-title":"J. Symb. Log."},{"key":"9023_CR12","doi-asserted-by":"crossref","first-page":"1963","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. J. Symb. Log. 54, 1963\u20131079 (1989)","journal-title":"J. Symb. Log."},{"key":"9023_CR13","doi-asserted-by":"crossref","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. Z.\u00a0Math. Log. Grundl. Math. 36, 29\u201346 (1990)","journal-title":"Z.\u00a0Math. Log. Grundl. Math."},{"issue":"1","key":"9023_CR14","doi-asserted-by":"crossref","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 2 1 and EF. Inf. Comput. 140(1), 82\u201394 (1998)","journal-title":"Inf. Comput."},{"key":"9023_CR15","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial-time reducibility. J. ACM 22, 155\u2013171 (1975)","journal-title":"J. ACM"},{"key":"9023_CR16","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0304-3975(02)00411-5","volume":"295","author":"P. Pudl\u00e1k","year":"2003","unstructured":"Pudl\u00e1k, P.: On reducibility and symmetry of disjoint $\\mathsf{NP}$ -pairs. Theor. Comput. Sci. 295, 323\u2013339 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9023_CR17","doi-asserted-by":"crossref","unstructured":"Razborov, A.A.: On provably disjoint $\\mathsf{NP}$ -pairs. Technical Report TR94-006, Electronic Colloquium on Computational Complexity (1994)","DOI":"10.7146\/brics.v1i36.21607"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9023-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9023-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9023-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:34Z","timestamp":1558698694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9023-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,29]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["9023"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9023-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6,29]]}}}