{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T04:10:45Z","timestamp":1743653445755,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_40","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"473-484","source":"Crossref","is-referenced-by-count":3,"title":["A Thirty Year Old Conjecture about Promise Problems"],"prefix":"10.1007","author":[{"given":"Andrew","family":"Hughes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Russell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan","family":"Selman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"40_CR1","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1145\/258533.258604","volume-title":"Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC 1997","author":"M. Ajtai","year":"1997","unstructured":"Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case\/average-case equivalence. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC 1997, pp. 284\u2013293. ACM, New York (1997)"},{"doi-asserted-by":"crossref","unstructured":"Agrawal, M.: Pseudo-random generators and structure of complete degrees. In: 17th Annual IEEE Conference on Computational Complexity, pp. 139\u2013145 (2002)","key":"40_CR2","DOI":"10.1109\/CCC.2002.1004349"},{"doi-asserted-by":"crossref","unstructured":"Adleman, L., Manders, K.: Reducibility, randomness, and intractability. In: Proc. 9th ACM Symp. Theory of Computing, pp. 151\u2013163 (1977)","key":"40_CR3","DOI":"10.1145\/800105.803405"},{"issue":"3","key":"40_CR4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jcss.1999.1674","volume":"61","author":"K. Ambos-Spies","year":"2000","unstructured":"Ambos-Spies, K., Bentzien, L.: Separating NP-completeness under strong hypotheses. Journal of Computer and System Sciences\u00a061(3), 335\u2013361 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"40_CR5","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a051, 177\u2013204 (1987)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"40_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(96)89424-2","volume":"168","author":"K. Ambos-Spies","year":"1996","unstructured":"Ambos-Spies, K., Neis, H., Terwijn, A.: Genericity and measure for exponential time. Theoretical Computer Science\u00a0168(1), 3\u201319 (1996)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"40_CR7","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0304-3975(95)00260-X","volume":"172","author":"K. Ambos-Spies","year":"1997","unstructured":"Ambos-Spies, K., Terwijn, A., Zheng, X.: Resource bounded randomness and weakly complete problems. Theoretical Computer Science\u00a0172(1), 195\u2013207 (1997)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"40_CR8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s00224-008-9163-5","volume":"47","author":"H. Buhrman","year":"2010","unstructured":"Buhrman, H., Hescott, B., Homer, S., Torenvliet, L.: Non-uniform reductions. Theory of Computing Systems\u00a047(2), 317\u2013241 (2010)","journal-title":"Theory of Computing Systems"},{"doi-asserted-by":"crossref","unstructured":"Balcazar, J., Mayordomo, E.: A note on genericty and bi-immunity. In: Proceedings of the Tenth Annual IEEE Conference on Computational Complexity, pp. 193\u2013196 (1995)","key":"40_CR9","DOI":"10.1109\/SCT.1995.514857"},{"issue":"2","key":"40_CR10","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","volume":"61","author":"S. Even","year":"1984","unstructured":"Even, S., Selman, A., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Information and Control\u00a061(2), 159\u2013173 (1984)","journal-title":"Information and Control"},{"unstructured":"Fortnow, L.: Personal Communication","key":"40_CR11"},{"doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169\u2013178 (2009)","key":"40_CR12","DOI":"10.1145\/1536414.1536440"},{"unstructured":"Gu, X., Hitchcock, J., Pavan, A.: Collapsing and separating completeness notions under average-case and worst-case hypotheses. In: STACS 2010. LIPIcs, vol.\u00a05, pp. 429\u2013440. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2010)","key":"40_CR13"},{"key":"40_CR14","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comp. System Sci.\u00a028, 270\u2013299 (1984)","journal-title":"J. Comp. System Sci."},{"key":"40_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/11685654_12","volume-title":"Theoretical Computer Science","author":"O. Goldreich","year":"2006","unstructured":"Goldreich, O.: On Promise Problems: A Survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Shimon Even Festchrift. LNCS, vol.\u00a03895, pp. 254\u2013290. Springer, Heidelberg (2006)"},{"issue":"2","key":"40_CR16","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\u2013355 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"40_CR17","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., Sengupta, S., Zhang, L.: Disjoint NP-pairs. SIAM J. Comput.\u00a033(6), 1369\u20131416 (2004)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"40_CR18","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., Zhang, L.: Canonical disjoint NP-pairs of propositional proof systems. Theoretical Computer Science\u00a0370(1), 60\u201373 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"40_CR19","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1016\/j.ic.2006.10.005","volume":"205","author":"J. Hitchcock","year":"2007","unstructured":"Hitchcock, J., Pavan, A.: Comparing reductions to NP-complete sets. Information and Computation\u00a0205(5), 694\u2013706 (2007); In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 465\u2013476. Springer, Heidelberg (2006)","journal-title":"Information and Computation"},{"key":"40_CR20","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(95)00189-1","volume":"164","author":"J.H. Lutz","year":"1996","unstructured":"Lutz, J.H., Mayordomo, E.: Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science\u00a0164, 141\u2013163 (1996)","journal-title":"Theoretical Computer Science"},{"key":"40_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BFb0055731","volume-title":"Advances in Cryptology - CRYPTO \u201998","author":"P.Q. Nguy\u00ean","year":"1998","unstructured":"Nguy\u00ean, P.Q., Stern, J.: Cryptanalysis of the Ajtai-Dwork Cryptosystem. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol.\u00a01462, pp. 223\u2013242. Springer, Heidelberg (1998)"},{"issue":"3","key":"40_CR22","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1137\/S0097539701387039","volume":"31","author":"A. Pavan","year":"2002","unstructured":"Pavan, A., Selman, A.: Separation of NP-completeness notions. SIAM Journal on Computing\u00a031(3), 906\u2013918 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"40_CR23","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.ic.2003.05.001","volume":"188","author":"A. Pavan","year":"2004","unstructured":"Pavan, A., Selman, A.: Bi-immunity separates strong NP-completeness notions. Information and Computation\u00a0188, 116\u2013126 (2004)","journal-title":"Information and Computation"},{"doi-asserted-by":"crossref","unstructured":"Pudlak, P.: On reducibility and symmetry of disjoint NP-pairs. In: Electronic Colloquium on Computational Complexity, technical reports (2001)","key":"40_CR24","DOI":"10.1007\/3-540-44683-4_54"},{"doi-asserted-by":"crossref","unstructured":"Razborov, A.: On provably disjoint NP pairs. Technical Report 94-006, ECCC (1994)","key":"40_CR25","DOI":"10.7146\/brics.v1i36.21607"},{"key":"40_CR26","doi-asserted-by":"publisher","first-page":"233","DOI":"10.2307\/2964680","volume":"25","author":"J. Schoenfield","year":"1960","unstructured":"Schoenfield, J.: Degrees of models. Journal of Symbolic Logic\u00a025, 233\u2013237 (1960)","journal-title":"Journal of Symbolic Logic"},{"key":"40_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/BFb0012795","volume-title":"Automata, Languages, and Programming","author":"A. Selman","year":"1982","unstructured":"Selman, A., Yacobi, Y.: The Complexity of Promise Problems. In: Nielsen, M., Schmidt, E.M. (eds.) ICALP 1982. LNCS, vol.\u00a0140, pp. 502\u2013509. Springer, Heidelberg (1982)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T12:11:58Z","timestamp":1743595918000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}