{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:32:22Z","timestamp":1725456742979},"publisher-location":"Berlin\/Heidelberg","reference-count":25,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540529535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029598","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T05:33:46Z","timestamp":1133415226000},"page":"88-104","source":"Crossref","is-referenced-by-count":0,"title":["One-way functions in complexity theory"],"prefix":"10.1007","author":[{"given":"Alan L.","family":"Selman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","unstructured":"L. Berman. Polynomial Reducibilities and Complete Sets. PhD thesis, Cornell University, 1977."},{"key":"7_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\u2013322, 1977.","journal-title":"SIAM J. Comput."},{"key":"7_CR3","volume-title":"Complete problems, creative sets and isomorphism conjectures","author":"K. Ganesan","year":"1989","unstructured":"K. Ganesan. Complete problems, creative sets and isomorphism conjectures. PhD thesis, Boston University, Boston, MA, 1989."},{"key":"7_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, pages 495\u2013503, 1984.","DOI":"10.1109\/SFCS.1984.715952"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"J. Grollmann and A. Selman. Complexity measures for public-key cryptosystems. SIAM J. Comput., 11(2):, April 1988.","DOI":"10.1137\/0217018"},{"key":"7_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\u2013237, 1985.","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR7","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. Theoretical Computer Science, 47:263\u2013276, 1987.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"7_CR8","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\u2013796, Nov. 1981.","journal-title":"SIAM J. Comput."},{"key":"7_CR9","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 Comput., pages 157\u2013166, 1989.","DOI":"10.1145\/73007.73022"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. The structure of complete degrees. In A. Selman, editor, Complexity Theory Retrospective, pages 108\u2013146, Springer-Verlag, 1990.","DOI":"10.1007\/978-1-4612-4478-3_7"},{"key":"7_CR11","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\u201330, 1985.","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR12","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. Computer Systems Sci., 36:490\u2013509, 1988.","journal-title":"J. Computer Systems Sci."},{"key":"7_CR13","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. Comp. System Sci., 13:300\u2013317, 1976.","journal-title":"J. Comp. System Sci."},{"issue":"2","key":"7_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. Theor. Comput. Sci., 39(2):207\u2013224, August 1985.","journal-title":"Theor. Comput. Sci."},{"key":"7_CR15","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1002\/malq.19550010205","volume":"1","author":"J. Myhill","year":"1955","unstructured":"J. Myhill. Creative sets. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 1:97\u2013108, 1955.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"7_CR16","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\u2013316, 1944.","journal-title":"Bull. Amer. Math. Soc."},{"issue":"4","key":"7_CR17","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\u2013457, November 1978.","journal-title":"SIAM J. Comput."},{"key":"7_CR18","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\u2013996, 1988.","journal-title":"SIAM J. Comput."},{"key":"7_CR19","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\u2013479, 1983.","journal-title":"SIAM J. Comput."},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"S. Toda. On the computational power of PP and \u2295P. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 514\u2013519, 1989.","DOI":"10.1109\/SFCS.1989.63527"},{"issue":"1","key":"7_CR21","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. Information Processing Letters, 5(1):20\u201323, May 1976.","journal-title":"Information Processing Letters"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"J. Wang. Some remarks on polynomial time isomorphisms. manuscript, 1990.","DOI":"10.1007\/3-540-53504-7_71"},{"key":"7_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, pages 24\u201333, 1989.","DOI":"10.1109\/SCT.1989.41811"},{"key":"7_CR24","volume-title":"Polynomial time creativity and its applications","author":"J. Wang","year":"1990","unstructured":"J. Wang. Polynomial time creativity and its applications. PhD thesis, Boston University, Boston, MA, 1990."},{"key":"7_CR25","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\u2013165, 1985.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1990"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029598","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T08:15:11Z","timestamp":1586592911000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029598"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540529535"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/bfb0029598","relation":{},"subject":[]}}