{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:44Z","timestamp":1725664184827},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_110","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:00:11Z","timestamp":1330275611000},"page":"619-627","source":"Crossref","is-referenced-by-count":1,"title":["Beyond PNP=NEXP"],"prefix":"10.1007","author":[{"given":"Stephen A.","family":"Fenner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lance J.","family":"Fortnow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"54_CR1","unstructured":"L. Berman. Polynomial Reducibilities and Complete Sets. PhD thesis, Cornell University, 1977."},{"key":"54_CR2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"1","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis. On isomorphism and density of NP and other complete sets. SIAM Journal on Computing, 1:305\u2013322, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"54_CR3","first-page":"118","volume-title":"Generic oracles and oracle classes","author":"M. Blum","year":"1987","unstructured":"M. Blum and R. Impagliazzo. Generic oracles and oracle classes. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, pages 118\u2013126, New York, 1987. IEEE."},{"key":"54_CR4","doi-asserted-by":"crossref","unstructured":"H. Buhrman and L. Torenvliet. On the cutting edge of relativization: The resource bounded injury method. In Proceedings of the 21st International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science. Springer-Verlag, 1994. To appear.","DOI":"10.1007\/3-540-58201-0_74"},{"key":"54_CR5","doi-asserted-by":"crossref","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. The isomorphism conjecture holds relative to an oracle. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages 30\u201339, 1992. To appear in SIAM J. Comp.","DOI":"10.1109\/SFCS.1992.267821"},{"key":"54_CR6","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/BF01195202","volume":"27","author":"B. Fu","year":"1994","unstructured":"B. Fu, H. Li, and Y. Zhong. An application of the translational method. Mathematical Systems Theory, 27:183\u2013186, 1994.","journal-title":"Mathematical Systems Theory"},{"key":"54_CR7","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 Journal on Computing, 17:309\u2013335, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"54_CR8","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0304-3975(91)90323-T","volume":"81","author":"J. Hartmanis","year":"1991","unstructured":"J. Hartmanis and L. Hemachandra. One-way functions and the nonisomorphism of NP-complete sets. Theoretical Computer Science, 81(1):155\u2013163, 1991.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"54_CR9","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0022-0000(92)90023-C","volume":"44","author":"S. Homer","year":"1992","unstructured":"S. Homer and A. Selman. Oracles for structural properties: The isomorphism problem and public-key cryptography. Journal of Computer and System Sciences, 44(2):287\u2013301, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"54_CR10","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass., 1979."},{"key":"54_CR11","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"},{"key":"54_CR12","first-page":"53","volume-title":"Using bounded query classes to separate classes in the exponential time hierarchy from classes in PH","author":"S. Mocas","year":"1994","unstructured":"S. Mocas. Using bounded query classes to separate classes in the exponential time hierarchy from classes in PH. In Proceedings of the 9th IEEE Structure in Complexity Theory Conference, pages 53\u201358. IEEE, New York, 1994."},{"issue":"1","key":"54_CR13","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/322290.322306","volume":"29","author":"C. Rackoff","year":"1982","unstructured":"C. Rackoff. Relativized questions involving probabilistic algorithms. Journal of the ACM, 29(1):261\u2013268, 1982.","journal-title":"Journal of the ACM"},{"key":"54_CR14","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A. Selman","year":"1979","unstructured":"A. Selman. P-selective sets, tally languages, and the behavior of polynomial-time reducibilities on NP. Mathematical Systems Theory, 13:55\u201365, 1979.","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"54_CR15","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. Seiferas","year":"1978","unstructured":"J. Seiferas, M. Fischer, and A. Meyer. Separating nondeterministic time complexity classes. Journal of the ACM, 25(1):146\u2013167, 1978.","journal-title":"Journal of the ACM"},{"key":"54_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-02460-7","volume-title":"Recursively Enumerable Sets and Degrees","author":"R. I. Soare","year":"1987","unstructured":"R. I. Soare. Recursively Enumerable Sets and Degrees. Springer-Verlag, Berlin, 1987."}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_110.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:22:09Z","timestamp":1619572929000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_110","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}