{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T16:24:25Z","timestamp":1756571065775},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,4,14]],"date-time":"2011-04-14T00:00:00Z","timestamp":1302739200000},"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":[[2012,8]]},"DOI":"10.1007\/s00224-011-9326-7","type":"journal-article","created":{"date-parts":[[2011,4,13]],"date-time":"2011-04-13T06:07:04Z","timestamp":1302674824000},"page":"229-247","source":"Crossref","is-referenced-by-count":2,"title":["Inseparability and Strong Hypotheses for Disjoint NP Pairs"],"prefix":"10.1007","volume":"51","author":[{"given":"Lance","family":"Fortnow","sequence":"first","affiliation":[]},{"given":"Jack H.","family":"Lutz","sequence":"additional","affiliation":[]},{"given":"Elvira","family":"Mayordomo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,4,14]]},"reference":[{"key":"9326_CR1","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(87)90053-3","volume":"51","author":"K. Ambos-Spies","year":"1987","unstructured":"Ambos-Spies, K., Fleischhack, H., Huwig, H.: Diagonalizations over polynomial time computable sets. Theor. Comput. Sci. 51, 177\u2013204 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"9326_CR2","series-title":"Lecture Notes in Pure and Applied Mathematics","first-page":"1","volume-title":"Complexity, Logic and Recursion Theory","author":"K. Ambos-Spies","year":"1997","unstructured":"Ambos-Spies, K., Mayordomo, E.: Resource-bounded measure and randomness. In: Sorbi, A. (ed.) Complexity, Logic and Recursion Theory. Lecture Notes in Pure and Applied Mathematics, pp.\u00a01\u201347. Marcel Dekker, New York (1997)"},{"key":"9326_CR3","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/S0304-3975(95)00260-X","volume":"172","author":"K. Ambos-Spies","year":"1997","unstructured":"Ambos-Spies, K., Terwijn, S.A., Zheng, X.: Resource bounded randomness and weakly complete problems. Theor. Comput. Sci. 172, 195\u2013207 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"9326_CR4","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"Baker, T., Gill, J., Solovay, R.: Relativizations of the P =? NP question. SIAM J. Comput. 4, 431\u2013442 (1975)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9326_CR5","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1137\/S0097539796302269","volume":"29","author":"J.M. Breutzmann","year":"1999","unstructured":"Breutzmann, J.M., Lutz, J.H.: Equivalence of measures of complexity classes. SIAM J. Comput. 29(1), 302\u2013326 (1999)","journal-title":"SIAM J. Comput."},{"key":"9326_CR6","doi-asserted-by":"crossref","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. J. Symb. Log. 44, 36\u201350 (1979)","journal-title":"J. Symb. Log."},{"issue":"2","key":"9326_CR7","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","volume":"61","author":"S. Even","year":"1984","unstructured":"Even, S., Selman, A.L., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Inf. Control 61(2), 159\u2013173 (1984)","journal-title":"Inf. Control"},{"key":"9326_CR8","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s00037-002-0173-4","volume":"11","author":"L. Fortnow","year":"2002","unstructured":"Fortnow, L., Rogers, J.: Separability and one-way functions. Comput. Complex. 11, 137\u2013157 (2002)","journal-title":"Comput. Complex."},{"key":"9326_CR9","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 NP-pairs. Inf. Comput. 200, 247\u2013267 (2005)","journal-title":"Inf. Comput."},{"key":"9326_CR10","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, 1369\u20131416 (2004)","journal-title":"SIAM J. Comput."},{"key":"9326_CR11","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/11685654_11","volume-title":"Theoretical Computer Science: Essays 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: Theoretical Computer Science: Essays in Memory of Shimon Even, pp.\u00a0241\u2013253. Springer, Berlin (2006)"},{"key":"9326_CR12","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 370, 60\u201373 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9326_CR13","series-title":"LNCS","first-page":"307","volume-title":"COCOON","author":"C. Gla\u00dfer","year":"2007","unstructured":"Gla\u00dfer, C., Selman, A.L., Zhang, L.: The informational content of canonical disjoint NP-pairs. In: COCOON. LNCS, pp.\u00a0307\u2013317. Springer, Berlin (2007)"},{"key":"9326_CR14","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1007\/11685654_12","volume-title":"Theoretical Computer Science: Essays in Memory of Shimon Even","author":"O. Goldreich","year":"2006","unstructured":"Goldreich, O.: On promise problems: A survey. In: Theoretical Computer Science: Essays in Memory of Shimon Even, pp.\u00a0254\u2013290. Springer, Berlin (2006)"},{"key":"9326_CR15","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/0217018","volume":"11","author":"J. Grollmann","year":"1988","unstructured":"Grollmann, J., Selman, A.: Complexity measures for public-key cryptosystems. SIAM J. Comput. 11, 309\u2013335 (1988)","journal-title":"SIAM J. Comput."},{"key":"9326_CR16","unstructured":"Hitchcock, J.M.: Resource-bounded measure bibliography. http:\/\/www.cs.uwyo.edu\/~jhitchco\/bib\/rbm.shtml"},{"key":"9326_CR17","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0022-0000(92)90023-C","volume":"44","author":"S. Homer","year":"1992","unstructured":"Homer, S., Selman, A.L.: Oracles for structural properties: The isomorphism problem and public-key cryptography. J. Comput. Syst. Sci. 44, 287\u2013301 (1992)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9326_CR18","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0304-3975(95)80030-D","volume":"143","author":"D.W. Juedes","year":"1995","unstructured":"Juedes, D.W., Lutz, J.H.: Weak completeness in E and E 2. Theor. Comput. Sci. 143(1), 149\u2013158 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9326_CR19","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1109\/CCC.2000.856739","volume-title":"Proceedings of the 15th Annual IEEE Conference on Computational Complexity","author":"J. Kahn","year":"2000","unstructured":"Kahn, J., Saks, M.E., Smyth, C.D.: A\u00a0dual version of reimer\u2019s inequality and a proof of rudich\u2019s conjecture. In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pp.\u00a098\u2013103 (2000)"},{"key":"9326_CR20","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1006\/jcss.1996.0065","volume":"53","author":"S.M. Kautz","year":"1996","unstructured":"Kautz, S.M., Miltersen, P.B.: Relative to a random oracle, NP is not small. J. Comput. Syst. Sci. 53, 235\u2013250 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9326_CR21","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0304-3975(98)00067-X","volume":"207","author":"A.K. Lorentz","year":"1998","unstructured":"Lorentz, A.K., Lutz, J.H.: Genericity and randomness over feasible probability measures. Theor. Comput. Sci. 207(1), 245\u2013259 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9326_CR22","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J.H. Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci. 44(2), 220\u2013258 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"9326_CR23","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/978-1-4612-1872-2_10","volume-title":"Complexity Theory Retrospective II","author":"J.H. Lutz","year":"1997","unstructured":"Lutz, J.H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp.\u00a0225\u2013254. Springer, Berlin (1997)"},{"key":"9326_CR24","first-page":"83","volume-title":"Current Trends in Theoretical Computer Science, entering the 21st century","author":"J.H. Lutz","year":"2001","unstructured":"Lutz, J.H., Mayordomo, E.: Twelve problems in resource-bounded measure. In: P\u0103un, G., Rozenberg, G., Salomaa, A. (eds.) Current Trends in Theoretical Computer Science, entering the 21st century, pp.\u00a083\u2013101. Singapore, World Scientific (2001)"},{"key":"9326_CR25","doi-asserted-by":"crossref","unstructured":"Razborov, A.: On provably disjoint NP pairs. Technical report 94-006, ECCC (1994)","DOI":"10.7146\/brics.v1i36.21607"},{"key":"9326_CR26","series-title":"Proc. Sympos. Appl. Math.","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1090\/psapm\/038\/1020811","volume-title":"Computational complexity theory","author":"A.L. Selman","year":"1989","unstructured":"Selman, A.L.: Complexity issues in cryptography. In: Computational complexity theory, Atlanta, GA, 1988. Proc. Sympos. Appl. Math., vol.\u00a038, pp.\u00a092\u2013107. Amer. Math. Soc., Providence (1989)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9326-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9326-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9326-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T00:23:03Z","timestamp":1560126183000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9326-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4,14]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["9326"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9326-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,14]]}}}