{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T03:17:41Z","timestamp":1778296661129,"version":"3.51.4"},"reference-count":25,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,10,1]],"date-time":"2003-10-01T00:00:00Z","timestamp":1064966400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3613,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2003,10]]},"DOI":"10.1016\/s0890-5401(03)00119-6","type":"journal-article","created":{"date-parts":[[2003,6,21]],"date-time":"2003-06-21T01:34:55Z","timestamp":1056159295000},"page":"90-103","source":"Crossref","is-referenced-by-count":20,"title":["Inverting onto functions"],"prefix":"10.1016","volume":"186","author":[{"given":"Stephen A.","family":"Fenner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashish V.","family":"Naik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John D.","family":"Rogers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0890-5401(03)00119-6_BIB1","doi-asserted-by":"crossref","unstructured":"L. Babai, Trading group theory for randomness, in: Proceedings of 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 421\u2013429","DOI":"10.1145\/22145.22192"},{"key":"10.1016\/S0890-5401(03)00119-6_BIB2","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","article-title":"Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes","volume":"36","author":"Babai","year":"1988","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"10.1016\/S0890-5401(03)00119-6_BIB3","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","article-title":"Relativizations of the P=? NP question","volume":"4","author":"Baker","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0890-5401(03)00119-6_BIB4","doi-asserted-by":"crossref","unstructured":"P. Beame, S. Cook, J. Edmonds, R. Impagliazzo, T. Pitassi, The relative complexity of NP search problems, in: Proceedings of 27th ACM Symposium on Theory of Computing, 1995, pp. 303\u2013314","DOI":"10.1145\/225058.225147"},{"key":"10.1016\/S0890-5401(03)00119-6_BIB5","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","article-title":"Relative to a random oracle A, PA\u2260NPA\u2260Co-NPA with probability 1","volume":"10","author":"Bennett","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0890-5401(03)00119-6_BIB6","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","article-title":"On isomorphisms and density of NP and other complete sets","volume":"6","author":"Berman","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0890-5401(03)00119-6_BIB7","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1137\/0213030","article-title":"Quantitative relativizations of complexity classes","volume":"13","author":"Book","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0890-5401(03)00119-6_BIB8","unstructured":"A. Borodin, A. Demers, Some comments on functional self-reducibility and the NP hierarchy, Technical Report TR76-284, Cornell University, Department of Computer Science, Upson Hall, Ithaca, NY 14853, 1976"},{"key":"10.1016\/S0890-5401(03)00119-6_BIB9","doi-asserted-by":"crossref","unstructured":"S. Cook, The complexity of theorem-proving procedures, in: Proceedings of 13th Annual ACM Symposium on Theory of Computing, 1971, pp. 151\u2013158","DOI":"10.1145\/800157.805047"},{"key":"10.1016\/S0890-5401(03)00119-6_BIB10","doi-asserted-by":"crossref","unstructured":"P. Crescenzi, R. Silvestri, Sperner\u2019s lemma and Robust Machines, in: Proceedings of 8th Annual Structure in Complexity Theory, 1993, pp. 194\u2013199","DOI":"10.1109\/SCT.1993.336527"},{"issue":"1","key":"10.1016\/S0890-5401(03)00119-6_BIB11","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/S0097539793248305","article-title":"The isomorphism conjecture holds relative to an oracle","volume":"25","author":"Fenner","year":"1996","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0890-5401(03)00119-6_BIB12","series-title":"Proccedings of 5th International Symposium on Algorithms and Computation","first-page":"396","article-title":"Separability and one-way functions","author":"Fortnow","year":"1994"},{"key":"10.1016\/S0890-5401(03)00119-6_BIB13","series-title":"Randomness and Computation","first-page":"429","article-title":"On completeness and soundness in interactive proof systems","volume":"vol. 5","author":"Furer","year":"1989"},{"issue":"3","key":"10.1016\/S0890-5401(03)00119-6_BIB14","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1145\/116825.116852","article-title":"Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems","volume":"38","author":"Goldreich","year":"1991","journal-title":"JACM"},{"key":"10.1016\/S0890-5401(03)00119-6_BIB15","doi-asserted-by":"crossref","unstructured":"J. Grollmann, A. Selman, Complexity measures for public-key cryptosystems, in: Proceedings of 25th IEEE Symposium on Foundations of Computer Science, 1984, pp. 495\u2013503","DOI":"10.1109\/SFCS.1984.715952"},{"key":"10.1016\/S0890-5401(03)00119-6_BIB16","doi-asserted-by":"crossref","DOI":"10.1137\/0217018","article-title":"Complexity measures for public-key cryptosystems","volume":"17","author":"Grollmann","year":"1988","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10.1016\/S0890-5401(03)00119-6_BIB17","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1137\/S0097539794268315","article-title":"Computing unique solutions collapses the polynomial hierarchy","volume":"25","author":"Hemaspaandra","year":"1996","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0890-5401(03)00119-6_BIB18","unstructured":"L. Hemaspaandra, J. Rothe, G. Wechsung, Easy sets and hard certificate schemes, Technical Report MATH\/95\/5, Friedrich-Schiller-Universit\u00e4t Jena, May 1995"},{"key":"10.1016\/S0890-5401(03)00119-6_BIB19","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, M. Naor, Decision trees and downward closures, in: Proceedings of 3rd Annual Conference on Structure in Complexity Theory, 1988, pp. 29\u201338","DOI":"10.1109\/SCT.1988.5260"},{"key":"10.1016\/S0890-5401(03)00119-6_BIB20","series-title":"Complexity of Computer Computations","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1016\/S0890-5401(03)00119-6_BIB21","doi-asserted-by":"crossref","unstructured":"S. Kurtz, S. Mahaney, J. Royer, The isomorphism conjecture fails relative to a random oracle, in: Proceedings of 21st Annual ACM Symposium on Theory of Computations, 1989, pp. 157\u2013166","DOI":"10.1109\/SCT.1989.41808"},{"key":"10.1016\/S0890-5401(03)00119-6_BIB22","first-page":"265","article-title":"Universal sorting problems","volume":"9","author":"Levin","year":"1973","journal-title":"Probl. Inf. Transmiss."},{"key":"10.1016\/S0890-5401(03)00119-6_BIB23","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","article-title":"On the complexity of the parity argument and other inefficient proofs of existence","author":"Papadimitriou","year":"1994","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10.1016\/S0890-5401(03)00119-6_BIB24","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/S0022-0000(05)80009-1","article-title":"A taxonomy of complexity classes of functions","volume":"48","author":"Selman","year":"1994","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/S0890-5401(03)00119-6_BIB25","series-title":"Proceedings of the 8th IEEE Structure in Complexity Theory Conference","first-page":"132","article-title":"Relationships between NP-sets, Co-NP-sets and P-sets relative to random oracles","author":"Vereshchagin","year":"1993"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540103001196?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540103001196?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T01:25:16Z","timestamp":1553045116000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540103001196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,10]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,10]]}},"alternative-id":["S0890540103001196"],"URL":"https:\/\/doi.org\/10.1016\/s0890-5401(03)00119-6","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2003,10]]}}}