{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T13:52:57Z","timestamp":1773237177580,"version":"3.50.1"},"reference-count":14,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1984,5,1]],"date-time":"1984-05-01T00:00:00Z","timestamp":452217600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,18]],"date-time":"2013-07-18T00:00:00Z","timestamp":1374105600000},"content-version":"vor","delay-in-days":10670,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Control"],"published-print":{"date-parts":[[1984,5]]},"DOI":"10.1016\/s0019-9958(84)80056-x","type":"journal-article","created":{"date-parts":[[2005,5,6]],"date-time":"2005-05-06T22:48:44Z","timestamp":1115419724000},"page":"159-173","source":"Crossref","is-referenced-by-count":183,"title":["The complexity of promise problems with applications to public-key cryptography"],"prefix":"10.1016","volume":"61","author":[{"given":"Shimon","family":"Even","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan L.","family":"Selman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yacov","family":"Yacobi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0019-9958(84)80056-X_bib1","series-title":"Qualitative controlled relativizations of complexity classes","author":"Book","year":"1982"},{"issue":"No. 2","key":"10.1016\/S0019-9958(84)80056-X_bib2","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1109\/TIT.1979.1056010","article-title":"A note on the complexity of cryptography","volume":"IT-25","author":"Brassard","year":"1979","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"No. 6","key":"10.1016\/S0019-9958(84)80056-X_bib3","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1109\/TIT.1983.1056754","article-title":"Relativized cryptography","volume":"IT-29","author":"Brassard","year":"1983","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/S0019-9958(84)80056-X_bib4","series-title":"Proc. 7th Colloq. Automata, Lang. Programming","first-page":"195","article-title":"Cryptography and NP-completeness","volume":"Vol. 85","author":"Even","year":"1980"},{"key":"10.1016\/S0019-9958(84)80056-X_bib5","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0019-9958(84)80056-X_bib6","series-title":"Relativizations of unambiguous and random polynomial time classes","author":"Geske","year":"1983"},{"key":"10.1016\/S0019-9958(84)80056-X_bib7","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","article-title":"On the structure of polynomial time reducibility","volume":"22","author":"Ladner","year":"1975","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0019-9958(84)80056-X_bib8","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","article-title":"A comparison of polynomial time reducibilities","volume":"1","author":"Ladner","year":"1975","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0019-9958(84)80056-X_bib9","series-title":"Proc. 14th Ann. ACM Sympos. on Theory of Computing","first-page":"255","article-title":"The complexity of facets (and some facets of complexity)","author":"Papadimitriou","year":"1982"},{"key":"10.1016\/S0019-9958(84)80056-X_bib10","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/322290.322306","article-title":"Relativized questions involving probabilistic algorithms","volume":"29","author":"Rackoff","year":"1982","journal-title":"J. Assoc. Comput. Mach."},{"issue":"No. 6","key":"10.1016\/S0019-9958(84)80056-X_bib11","first-page":"310","article-title":"On the structure of NP","volume":"21","author":"Selman","year":"1974","journal-title":"Notices Amer. Math. Soc."},{"key":"10.1016\/S0019-9958(84)80056-X_bib12","series-title":"Proc. 9th Colloq. Automata, Lang. Programming","first-page":"523","article-title":"On relativization and the existence of complete sets","volume":"Vol. 140","author":"Sipser","year":"1982"},{"key":"10.1016\/S0019-9958(84)80056-X_bib13","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0019-9958(67)90401-9","article-title":"Partial algorithm problems for context-free languages","volume":"11","author":"Ullian","year":"1967","journal-title":"Inform. Contr."},{"key":"10.1016\/S0019-9958(84)80056-X_bib14","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","article-title":"Relative complexity of checking and evaluating","volume":"5","author":"Valiant","year":"1976","journal-title":"Inform. Process."}],"container-title":["Information and Control"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S001999588480056X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S001999588480056X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,26]],"date-time":"2019-01-26T17:27:49Z","timestamp":1548523669000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S001999588480056X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,5]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1984,5]]}},"alternative-id":["S001999588480056X"],"URL":"https:\/\/doi.org\/10.1016\/s0019-9958(84)80056-x","relation":{},"ISSN":["0019-9958"],"issn-type":[{"value":"0019-9958","type":"print"}],"subject":[],"published":{"date-parts":[[1984,5]]}}}