{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:36Z","timestamp":1759638996077},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1992,9,1]],"date-time":"1992-09-01T00:00:00Z","timestamp":715305600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1992,9]]},"DOI":"10.1007\/bf01374525","type":"journal-article","created":{"date-parts":[[2005,4,3]],"date-time":"2005-04-03T08:24:12Z","timestamp":1112516652000},"page":"203-221","source":"Crossref","is-referenced-by-count":45,"title":["A survey of one-way functions in complexity theory"],"prefix":"10.1007","volume":"25","author":[{"given":"Alan L.","family":"Selman","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","volume-title":"Ph.D. thesis","author":"L. Berman","year":"1977","unstructured":"L. Berman. Polynomial Reducibilities and Complete Sets. Ph.D. thesis, Cornell University, Ithaca, NY, 1977."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and H. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM J. Comput., 6:305?322, 1977.","journal-title":"SIAM J. Comput."},{"key":"CR3","volume-title":"Ph.D. thesis","author":"K. Ganesan","year":"1989","unstructured":"K. Ganesan. Complete Problems, Creative Sets and Isomorphism Conjectures. Ph.D. thesis, Boston University, Boston, MA, 1989."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"J. Grollmann and A. Selman. Complexity measures for public-key cryptosystems. In Proc. 25th IEEE Symp. on Foundations of Computer Science, pp. 495?503, 1984.","DOI":"10.1109\/SFCS.1984.715952"},{"issue":"2","key":"CR5","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"J. Grollmann and A. Selman. Complexity measures for public-key cryptosystems. SIAM J. Comput., 17(2):309?335, 1988.","journal-title":"SIAM J. Comput."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0304-3975(85)90140-9","volume":"39","author":"D. Joseph","year":"1985","unstructured":"D. Joseph and P. Young. Some remarks on witness functions for non-polynomial and non-complete sets in NP. Theoret. Comput. Sci., 39:225?237, 1985.","journal-title":"Theoret. Comput. Sci."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/978-1-4612-4478-3_6","volume-title":"Complexity Theory Retrospective","author":"D. Joseph","year":"1990","unstructured":"D. Joseph and P. Young. Self-reducibility: the effects of internal structure on computational complexity. In A. Selman, editor, Complexity Theory Retrospective, pp. 82?107. Springer-Verlag, New York, 1990."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(85)90085-4","volume":"37","author":"K. Ko","year":"1985","unstructured":"K. Ko. On some natural complete operators. Theoret. Comput. Sci., 37:1?30, 1985.","journal-title":"Theoret. Comput. Sci."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(86)90152-0","volume":"47","author":"K. Ko","year":"1987","unstructured":"K. Ko, T. Long, and D. Du. A note on one-way functions and polynomial-time isomorphisms. Theoret. Comput. Sci., 47:263?276, 1987.","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"CR10","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1137\/0210061","volume":"10","author":"K. Ko","year":"1981","unstructured":"K. Ko and D. Moore. Completeness, approximation and density. SIAM J. Comput., 10(4): 787?796, 1981.","journal-title":"SIAM J. Comput."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. Krentel","year":"1988","unstructured":"M. Krentel. The complexity of optimization problems. J. Comput. System Sci., 36:490?509, 1988.","journal-title":"J. Comput. System Sci."},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. The isomorphism conjecture fails relative to a random oracle. In Proc. 21st Annual ACM Symp. on Theory of Computing, pp. 157?166, 1989.","DOI":"10.1145\/73007.73022"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/978-1-4612-4478-3_7","volume-title":"Complexity Theory Retrospective","author":"S. Kurtz","year":"1990","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. The structure of complete degrees. In A. Selman, editor, Complexity Theory Retrospective, pp. 108?146. Springer-Verlag, New York, 1990."},{"issue":"2","key":"CR14","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0304-3975(85)90139-2","volume":"39","author":"S. Mahaney","year":"1985","unstructured":"S. Mahaney and P. Young. Orderings of polynomial isomorphism types. Theoret. Comput. Sci, 39(2):207?224, 1985.","journal-title":"Theoret. Comput. Sci"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","volume":"13","author":"G. Miller","year":"1976","unstructured":"G. Miller. Reimann's hypothesis and tests for primality. J. Comput. System Sci, 13:300?317, 1976.","journal-title":"J. Comput. System Sci"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1002\/malq.19550010205","volume":"1","author":"J. Myhill","year":"1955","unstructured":"J. Myhill. Creative sets. Z. Math. Logik Grundlag. Math., 1:97?108, 1955.","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","volume":"50","author":"E. Post","year":"1944","unstructured":"E. Post. Recursively enumerable sets of integers and their decision problems. Bull. Amer. Math. Soc., 50:284?316, 1944.","journal-title":"Bull. Amer. Math. Soc."},{"issue":"4","key":"CR18","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1137\/0207035","volume":"7","author":"A. Selman","year":"1978","unstructured":"A. Selman. Polynomial time enumeration reducibility. SIAM J. Comput., 7(4):440?457, 1978.","journal-title":"SIAM J. Comput."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1137\/0217062","volume":"17","author":"A. Selman","year":"1988","unstructured":"A. Selman. Natural self-reducible sets. SIAM J. Comput., 17:989?996, 1988.","journal-title":"SIAM J. Comput."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/0212037","volume":"12","author":"A. Selman","year":"1983","unstructured":"A. Selman, Xu M.-R., and R. Book. Positive relativizations of complexity classes. SIAM J. Comput., 12:465?479, 1983.","journal-title":"SIAM J. Comput."},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"S. Toda. On the computational power of PP and ?P. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pp. 514?519, 1989.","DOI":"10.1109\/SFCS.1989.63527"},{"issue":"1","key":"CR22","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant. Relative complexity of checking and evaluating. Inform. Process. Lett., 5(1):20?23, 1976.","journal-title":"Inform. Process. Lett."},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"J. Wang. On P-creative sets vs. P-completely creative sets. In Proc. 4th IEEE Structure in Complexity Theory Conference, pp. 24?33, 1989.","DOI":"10.1109\/SCT.1989.41811"},{"key":"CR24","volume-title":"Ph.D. thesis","author":"J. Wang","year":"1990","unstructured":"J. Wang. Polynomial Time Creativity and Its Applications. Ph.D. thesis, Boston University, Boston, MA, 1990."},{"key":"CR25","doi-asserted-by":"crossref","unstructured":"J. Wang. Some remarks on polynomial time isomorphisms. Manuscript, 1990.","DOI":"10.1007\/3-540-53504-7_71"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0304-3975(85)90218-X","volume":"38","author":"O. Watanabe","year":"1985","unstructured":"O. Watanabe. On one-one polynomial time equivalence relations. Theoret. Comput. Sci., 38:157?165, 1985.","journal-title":"Theoret. Comput. Sci."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1007\/978-1-4612-4478-3_4","volume-title":"Complexity Theory Retrospective","author":"P. Young","year":"1990","unstructured":"P. Young. Juris Hartmanis: Fundamental contributions to isomorphism problems. In A, Selman, editor, Complexity Theory Retrospective, pp. 28?58. Springer-Verlag, New York, 1990."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01374525.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01374525\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01374525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T17:13:46Z","timestamp":1586193226000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01374525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,9]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,9]]}},"alternative-id":["BF01374525"],"URL":"https:\/\/doi.org\/10.1007\/bf01374525","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,9]]}}}