{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T21:53:08Z","timestamp":1672609988864},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,9,17]],"date-time":"2015-09-17T00:00:00Z","timestamp":1442448000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s00037-015-0107-6","type":"journal-article","created":{"date-parts":[[2015,9,17]],"date-time":"2015-09-17T07:54:51Z","timestamp":1442476491000},"page":"883-919","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A thirty Year old conjecture about promise problems"],"prefix":"10.1007","volume":"25","author":[{"given":"Andrew","family":"Hughes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debasis","family":"Mandal","sequence":"additional","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 L.","family":"Selman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,17]]},"reference":[{"key":"107_CR1","unstructured":"L. Adleman & K. Manders (1977). Reducibility, randomness, and intractability. In Proceedings of the 9th ACM Symposium on Theory of Computing, 151\u2013163"},{"key":"107_CR2","doi-asserted-by":"crossref","unstructured":"M. Agrawal (2002). Pseudo-random Generators and Structure of Complete Degrees. In 17th Annual IEEE Conference on Computational Complexity, 139\u2013147","DOI":"10.1109\/CCC.2002.1004349"},{"key":"107_CR3","doi-asserted-by":"crossref","unstructured":"M. Agrawal & O. Watanabe (2009). One-Way Functions and the Berman-Hartmanis Conjecture. In Proceedings of the 24th IEEE Conference on Computational Complexity, 194\u2013202","DOI":"10.1109\/CCC.2009.17"},{"key":"107_CR4","unstructured":"M. Ajtai & C. Dwork (1997). A public-key cryptosystem with worstcase\/average-case equivalence. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, 284\u2013293"},{"issue":"3","key":"107_CR5","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jcss.1999.1674","volume":"61","author":"K. Ambos-Spies","year":"2000","unstructured":"Ambos-Spies K., Bentzien L. (2000) Separating NP-completeness under strong hypotheses. Journal of Computer and System Sciences 61(3): 335\u2013361","journal-title":"Journal of Computer and System Sciences"},{"key":"107_CR6","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. (1987) Diagonalizations over polynomial time computable sets. Theoretical Computer Science 51: 177\u2013204","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"107_CR7","doi-asserted-by":"crossref","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. (1996) Genericity and measure for exponential time. Theoretical Computer Science 168(1): 3\u201319","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"107_CR8","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 A., Zheng X. (1997) Resource bounded randomness and weakly complete problems. Theoretical Computer Science 172(1): 195\u2013207","journal-title":"Theoretical Computer Science"},{"key":"107_CR9","doi-asserted-by":"crossref","unstructured":"J. Balcazar & E. Mayordomo (1995). A note on genericity and bi-immunity. In Proceedings of the Tenth Annual IEEE Conference on Computational Complexity, 193\u2013196","DOI":"10.1109\/SCT.1995.514857"},{"issue":"2","key":"107_CR10","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., Yacobi Y. (1984) The Complexity Of Promise ProblemsWith Applications To Public-Key Cryptography. Information and Control 61(2): 159\u2013173","journal-title":"Information and Control"},{"key":"107_CR11","doi-asserted-by":"crossref","unstructured":"C. Gentry (2009). Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st ACM Symposium on Theory of Computing, 169\u2013178","DOI":"10.1145\/1536414.1536440"},{"issue":"6","key":"107_CR12","doi-asserted-by":"crossref","first-page":"1369","DOI":"10.1137\/S0097539703425848","volume":"33","author":"C. Glasser","year":"2004","unstructured":"Glasser C., Selman A., Sengupta S., Zhang L. (2004) Disjoint NP-Pairs. SIAM Journal on Computing 33(6): 1369\u20131416","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"107_CR13","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.tcs.2006.10.006","volume":"370","author":"C. Glasser","year":"2007","unstructured":"Glasser C., Selman A., Zhang L. (2007) Canonical disjoint NP-pairs of propositional proof systems. Theoretical Computer Science 370(1): 60\u201373","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"107_CR14","first-page":"34","volume":"9","author":"C. Glasser","year":"2003","unstructured":"Glasser C., Wechsung G. (2003) Relativizing Function Classes. Journal of Universal Computer Science 9(1): 34\u201350","journal-title":"Journal of Universal Computer Science"},{"key":"107_CR15","doi-asserted-by":"crossref","unstructured":"O. Goldreich (2006). On Promise Problems: A Survey. In Theoretical Computer Science - Essays in Memory of Shimon Even, volume 3895 of Lecture Notes in Computer Science, 254\u2013290. Springer","DOI":"10.1007\/11685654_12"},{"key":"107_CR16","unstructured":"O. Goldreich & L. Levin (1989). A hard-core predicate for all oneway functions. In Proceedings of the 21st ACM Symposium on Theory of Computing, 25\u201332"},{"key":"107_CR17","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"Goldwasser S., Micali S. (1984) Probabilistic Encryption. Journal of Computer and System Sciences 28: 270\u2013299","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"107_CR18","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"Grollmann J., Selman A. (1988) Complexity measures for publickey cryptosystems. SIAM Journal on Computing 17(2): 309\u2013355","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"107_CR19","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad J., Impagliazzo R., Levin L., Luby M. (1999) A Pseudorandom Generator from any One-way Function. SIAM Journal on Computing 28(4): 364\u20131396","journal-title":"SIAM Journal on Computing"},{"key":"107_CR20","doi-asserted-by":"crossref","unstructured":"A. Hughes, A. Pavan, N. Russell & A. Selman (2012). A Thirty Year Old Conjecture about Promise Problems. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, 473\u2013484","DOI":"10.1007\/978-3-642-31594-7_40"},{"key":"107_CR21","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"A. Klivans","year":"2002","unstructured":"Klivans A., van Melkebeek D. (2002) Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing 31: 1501\u20131526","journal-title":"SIAM Journal on Computing"},{"key":"107_CR22","doi-asserted-by":"crossref","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. (1996) Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science 164: 141\u2013163","journal-title":"Theoretical Computer Science"},{"key":"107_CR23","doi-asserted-by":"crossref","unstructured":"P. Nguyen & J. Stern (1998). Cryptanalysis of the Ajtai-Dwork Cryptosystem. In Advances in Cryptology\u2014CRYPTO \u201998. 18th Annual International Cryptology Conference, Santa Barbara, California., volume 1462 of Lecture Notes in Computer Science, 223\u2013242. Springer","DOI":"10.1007\/BFb0055731"},{"issue":"3","key":"107_CR24","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1137\/S0097539701387039","volume":"31","author":"A. Pavan","year":"2002","unstructured":"Pavan A., Selman A. (2002) Separation of NP-completeness notions. SIAM Journal on Computing 31(3): 906\u2013918","journal-title":"SIAM Journal on Computing"},{"key":"107_CR25","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1016\/j.ic.2003.05.001","volume":"188","author":"A. Pavan","year":"2004","unstructured":"Pavan A., Selman A. (2004) Bi-immunity separates strong NP-completeness notions. Information and Computation 188: 116\u2013126","journal-title":"Information and Computation"},{"key":"107_CR26","doi-asserted-by":"crossref","unstructured":"P. Pudl\u00e1k (2001). On Reducibility and Symmetry of Disjoint NP-Pairs. In Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS), Marianske Lazne, Czech Republic, volume 2136 of Lecture Notes in Computer Science, 621\u2013632. Springer","DOI":"10.1007\/3-540-44683-4_54"},{"key":"107_CR27","doi-asserted-by":"crossref","unstructured":"A. Razborov (1994). On provably disjoint NP pairs. Technical Report 94-006, Electronic Colloquium on Computational Complexity","DOI":"10.7146\/brics.v1i36.21607"},{"key":"107_CR28","doi-asserted-by":"crossref","first-page":"233","DOI":"10.2307\/2964680","volume":"25","author":"J. Schoenfield","year":"1960","unstructured":"Schoenfield J. (1960) Degrees of models. Journal of Symbolic Logic 25: 233\u2013237","journal-title":"Journal of Symbolic Logic"},{"key":"107_CR29","doi-asserted-by":"crossref","unstructured":"A. Selman & Y. Yacobi (1982). The complexity of promise problems. In Proceedings of the 8th International Colloquium on Automata, Languages, and Programming, volume 140 of Lecture Notes in Computer Science, 502\u2013509. Springer-Verlag, Berlin","DOI":"10.1007\/BFb0012795"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0107-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-015-0107-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0107-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0107-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,30]],"date-time":"2019-08-30T17:29:04Z","timestamp":1567186144000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-015-0107-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,17]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["107"],"URL":"https:\/\/doi.org\/10.1007\/s00037-015-0107-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,17]]}}}