{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:42Z","timestamp":1725663402368},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_150","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:37:56Z","timestamp":1330209476000},"page":"393-404","source":"Crossref","is-referenced-by-count":4,"title":["Collapsing degrees via strong computation"],"prefix":"10.1007","author":[{"given":"Lane A.","family":"Hemachandra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Albrecht","family":"Hoene","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"issue":"6","key":"30_CR1","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1016\/0022-0000(88)90033-5","volume":"36","author":"E. Allender","year":"1988","unstructured":"E. Allender. Isomorphisms and 1-L reductions. Journal of Computer and System Sciences, 36(6):336\u2013350, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR2","volume-title":"Polynomial Reducibilities and Complete Sets","author":"L. Berman","year":"1977","unstructured":"L. Berman. Polynomial Reducibilities and Complete Sets. PhD thesis, Cornell University, Ithaca, NY, 1977."},{"key":"30_CR3","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"A. Blass and Y. Gurevich. On the unique satisfiability problem. Information and Control, 55:80\u201388, 1982.","journal-title":"Information and Control"},{"issue":"2","key":"30_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM Journal on Computing, 6(2):305\u2013322, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"30_CR5","unstructured":"G. Buntrock, L. Hemachandra, and D. Siefkes. Using inductive counting to simulate nondeterministic computation. Information and Computation. To appear."},{"key":"30_CR6","unstructured":"H. Buhrman, S. Homer, and L. Torenvliet. On complete sets for nondeterministic classes. Mathematical Systems Theory. To appear."},{"key":"30_CR7","doi-asserted-by":"crossref","unstructured":"R. Book. On separating complexity classes. In Proceedings of the 5th Structure in Complexity Theory Conference, pages 299\u2013304. IEEE Computer Society Press, July 1990.","DOI":"10.1109\/SCT.1990.113978"},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"K. Ganesan and S. Homer. Complete problems and strong polynomial reducibilities. In Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science, pages 240\u2013250. Springer-Verlag Lecture Notes in Computer Science #349, 1989.","DOI":"10.1007\/BFb0028988"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"J. Goldsmith and D. Joseph. Three results on the polynomial isomorphism of complete sets. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pages 390\u2013397, 1986.","DOI":"10.1109\/SFCS.1986.56"},{"key":"30_CR10","unstructured":"J. Hartmanis. Feasible Computations and Provable Complexity Properties. CBMSNSF Regional Conference Series in Applied Mathematics #30. SIAM, 1978."},{"issue":"3","key":"30_CR11","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0304-3975(78)90018-X","volume":"7","author":"J. Hartmanis","year":"1978","unstructured":"J. Hartmanis. On log-tape isomorphisms of complete sets. Theoretical Computer Science, 7(3):273\u2013286, 1978.","journal-title":"Theoretical Computer Science"},{"key":"30_CR12","unstructured":"J. Hartmanis and L. Hemachandra. One-way functions and the non-isomorphism of NP-complete sets. Theoretical Computer Science. To appear."},{"key":"30_CR13","series-title":"Technical Report","volume-title":"Collapsing degrees via strong computation","author":"L. Hemachandra","year":"1990","unstructured":"L. Hemachandra and A. Hoene. Collapsing degrees via strong computation. Technical Report TR-361, University of Rochester, Department of Computer Science, Rochester, NY, 14627, November 1990."},{"key":"30_CR14","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, N. Immerman, and S. Mahaney. One-way log-tape reductions. In Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, pages 65\u201371, 1978.","DOI":"10.1109\/SFCS.1978.31"},{"issue":"2","key":"30_CR15","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1137\/0210027","volume":"10","author":"J. Hartmanis","year":"1981","unstructured":"J. Hartmanis and S. Mahaney. Languages simultaneously complete for one-way and two-way log-tape automata. SIAM Journal on Computing, 10(2):383\u2013390, 1981.","journal-title":"SIAM Journal on Computing"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"S. Homer and A. Selman. Oracles for structural properties: the isomorphism problem and public-key cryptography. In Proceedings of the 4th Structure in Complexity Theory Conference, pages 3\u201314. IEEE Computer Society Press, June 1989.","DOI":"10.1109\/SCT.1989.41809"},{"key":"30_CR17","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17:935\u2013938, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"30_CR18","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. Theoretical Computer Science, 39:225\u2013237, 1985.","journal-title":"Theoretical Computer Science"},{"key":"30_CR19","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(86)90152-0","volume":"47","author":"K. Ko","year":"1986","unstructured":"K. Ko, T. Long, and D. Du. On one-way functions and polynomial-time isomorphisms. Theoretical Computer Science, 47:263\u2013276, 1986.","journal-title":"Theoretical Computer Science"},{"key":"30_CR20","doi-asserted-by":"crossref","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. Progress on collapsing degrees. In Proceedings of the 2nd Structure in Complexity Theory Conference, pages 126\u2013131. IEEE Computer Society Press, June 1987.","DOI":"10.1109\/PSCT.1987.10319261"},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. The isomorphism conjecture fails relative to a random oracle. In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 157\u2013166. ACM Press, May 1989.","DOI":"10.1145\/73007.73022"},{"key":"30_CR22","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":"30_CR23","series-title":"Technical Report","volume-title":"A relativized failure of the Berman-Hartmanis conjecture","author":"S. Kurtz","year":"1983","unstructured":"S. Kurtz. A relativized failure of the Berman-Hartmanis conjecture. Technical Report TR83-001, University of Chicago Department of Computer Science, Chicago, IL, 1983."},{"key":"30_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(82)90085-8","volume":"21","author":"T. Long","year":"1982","unstructured":"T. Long. Strong nondeterministic polynomial-time reducibilities. Theoretical Computer Science, 21:1\u201325, 1982.","journal-title":"Theoretical Computer Science"},{"key":"30_CR25","doi-asserted-by":"crossref","unstructured":"D. Russo. Optimal approximations of complete sets. In Proceedings of the 1st Structure in Complexity Theory Conference, pages 311\u2013324. Springer-Verlag Lecture Notes in Computer Science #223, June 1986.","DOI":"10.1007\/3-540-16486-3_107"},{"issue":"2","key":"30_CR26","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. Savitch","year":"1970","unstructured":"W. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177\u2013192, 1970.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"30_CR27","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 Journal on Computing, 7(4):440\u2013457, 1978.","journal-title":"SIAM Journal on Computing"},{"key":"30_CR28","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279\u2013284, 1988.","journal-title":"Acta Informatica"},{"key":"30_CR29","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. The relative complexity of checking and evaluating. Information Processing Letters, 5:20\u201323, 1976.","journal-title":"Information Processing Letters"},{"key":"30_CR30","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 P-equivalence relations. Theoretical Computer Science, 38:157\u2013165, 1985.","journal-title":"Theoretical Computer Science"},{"key":"30_CR31","doi-asserted-by":"crossref","unstructured":"P. Young. Juris Hartmanis: Fundamental contributions to isomorphism problems. In A. Selman, editor, Complexity Theory Retrospective, pages 28\u201358. Springer-Verlag, 1990.","DOI":"10.1007\/978-1-4612-4478-3_4"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_150.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T13:59:46Z","timestamp":1713621586000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_150"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_150","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}