{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,23]],"date-time":"2022-07-23T04:15:24Z","timestamp":1658549724556},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,8]]},"DOI":"10.1007\/s00224-008-9163-5","type":"journal-article","created":{"date-parts":[[2009,1,8]],"date-time":"2009-01-08T16:09:56Z","timestamp":1231430996000},"page":"317-341","source":"Crossref","is-referenced-by-count":5,"title":["Non-Uniform Reductions"],"prefix":"10.1007","volume":"47","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[]},{"given":"Benjamin","family":"Hescott","sequence":"additional","affiliation":[]},{"given":"Steven","family":"Homer","sequence":"additional","affiliation":[]},{"given":"Leen","family":"Torenvliet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,1,9]]},"reference":[{"key":"9163_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M.: Pseudo-random generators and structure of complete degrees. In IEEE Conference on Computational Complexity, pp. 139\u2013147 (2002)","DOI":"10.1109\/CCC.2002.1004349"},{"key":"9163_CR2","first-page":"75","volume-title":"Proc. Structure in Complexity Theory 7th Annual Conference","author":"M. Agrawal","year":"1993","unstructured":"Agrawal, M., Biswas, S.: Polynomial isomorphism of 1-L complete sets. In: Proc. Structure in Complexity Theory 7th Annual Conference, San Diego, California, pp. 75\u201380. IEEE Computer Society, Los Alamitos (1993)"},{"issue":"6","key":"9163_CR3","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1016\/0022-0000(88)90033-5","volume":"36","author":"E. Allender","year":"1988","unstructured":"Allender, E.: Isomorphisms and 1-L reductions. J. Comput. Syst. Sci. 36(6), 336\u2013350 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9163_CR4","first-page":"669","volume-title":"FOCS","author":"E. Allender","year":"2002","unstructured":"Allender, E., Buhrman, H., Kouck\u00fd, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. In: FOCS, pp. 669\u2013678. IEEE Computer Society, Los Alamitos (2002)"},{"key":"9163_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-13331-3_30","volume-title":"Logic and Machines","author":"K. Ambos-Spies","year":"1984","unstructured":"Ambos-Spies, K.: p-mitotic sets. In: B\u00f6rger, E., Hasenj\u00e4ger, G., Roding, D. (eds.) Logic and Machines. Lecture Notes in Computer Science, vol. 177, pp. 1\u201323. Springer, Berlin (1984)"},{"key":"9163_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I","author":"J. Balc\u00e1zar","year":"1988","unstructured":"Balc\u00e1zar, J., D\u00edaz, J., Gabarr\u00f3, J.: Structural Complexity I. Springer, Berlin (1988)"},{"key":"9163_CR7","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L., Hartmanis, H.: On isomorphisms and density of NP and other complete sets. SIAM J. Comput. 6, 305\u2013322 (1977)","journal-title":"SIAM J. Comput."},{"key":"9163_CR8","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1109\/SCT.1995.514858","volume-title":"Proceedings Structure in Complexity Theory, 10th Annual Conference (STRUCTURES95)","author":"H. Buhrman","year":"1995","unstructured":"Buhrman, H., Mayordomo, E.: An excursion to the Kolmogorov random strings. In: Proceedings Structure in Complexity Theory, 10th Annual Conference (STRUCTURES95), Minneapolis, pp. 197\u2013205. IEEE Computer Society, Los Alamitos (1995)"},{"key":"9163_CR9","first-page":"227","volume-title":"Proceedings 14th IEE Conference on Computational Complexity","author":"H. Buhrman","year":"1999","unstructured":"Buhrman, H., Torenvliet, L.: Complicated complementations. In: Proceedings 14th IEE Conference on Computational Complexity, pp. 227\u2013236. IEEE Computer Society, Los Alamitos (1999)"},{"key":"9163_CR10","first-page":"130","volume-title":"Proceedings 19th IEE Conference on Computational Complexity","author":"H. Buhrman","year":"2004","unstructured":"Buhrman, H., Torenvliet, L.: Separating complexity classes using structural properties. In: Proceedings 19th IEE Conference on Computational Complexity, pp. 130\u2013138. IEEE Computer Society, Los Alamitos (2004)"},{"key":"9163_CR11","unstructured":"Buhrman, H., Torenvliet, L.: A Post\u2019s program for complexity theory. In Bulletin of the EATCS 85, pp. 41\u201351 (2005)"},{"key":"9163_CR12","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF02090397","volume":"24","author":"H. Buhrman","year":"1991","unstructured":"Buhrman, H., Homer, S., Torenvliet, L.: On complete sets for nondeterministic classes. Math. Syst. Theory 24, 179\u2013200 (1991)","journal-title":"Math. Syst. Theory"},{"key":"9163_CR13","first-page":"83","volume-title":"Complexity Theory","author":"H. Buhrman","year":"1993","unstructured":"Buhrman, H., Spaan, E., Torenvliet, L.: Bounded reductions. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory, pp. 83\u201399. Cambridge University Press, Cambridge (1993)"},{"issue":"3","key":"9163_CR14","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/BF01271369","volume":"3","author":"H. Buhrman","year":"1993","unstructured":"Buhrman, H., Spaan, E., Torenvliet, L.: The relative power of logspace and polynomial time reductions. Comput. Complexity 3(3), 231\u2013244 (1993)","journal-title":"Comput. Complexity"},{"issue":"5","key":"9163_CR15","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1137\/S0097539798334736","volume":"29","author":"H. Buhrman","year":"2000","unstructured":"Buhrman, H., van Melkebeek, D., Fortnow, L., Torenvliet, L.: Using autoreducibility to separate complexity classes. SIAM J. Comput. 29(5), 1497\u20131520 (2000)","journal-title":"SIAM J. Comput."},{"key":"9163_CR16","doi-asserted-by":"crossref","unstructured":"Fenner, S., Fortnow, L., Kurtz, S.A.: The isomorphism conjecture holds relative to an oracle. In: Proc. 33rd IEEE Symposium Foundations of Computer Science, pp. 30\u201339 (1992)","DOI":"10.1109\/SFCS.1992.267821"},{"key":"9163_CR17","series-title":"Springer Lecture Notes in Computer Science","first-page":"240","volume-title":"Proc. Symposium on Theoretical Aspects of Computer Science","author":"K. Ganesan","year":"1988","unstructured":"Ganesan, K., Homer, S.: Complete problems and strong polynomial reducibilities. In: Proc. Symposium on Theoretical Aspects of Computer Science. Springer Lecture Notes in Computer Science, vol. 349, pp. 240\u2013250. Springer, Berlin (1988)"},{"key":"9163_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/978-3-540-77050-3_12","volume-title":"STTCS","author":"C. Gla\u00dfer","year":"2007","unstructured":"Gla\u00dfer, C., Selman, A.L., Travers, S.D., Zhang, L.: Non-mitotic sets. In: Arvind, V., Prasad, S. (eds.) STTCS. Lecture Notes in Computer Science, vol. 4855, pp. 146\u2013157. Springer, Berlin (2007)"},{"issue":"1","key":"9163_CR19","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0304-3975(91)90323-T","volume":"81","author":"J. Hartmanis","year":"1991","unstructured":"Hartmanis, J., Hemachandra, L.: One-way functions and the non-isomorphism of NP-complete sets. Theor. Comput. Sci. 81(1), 155\u2013163 (1991)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9163_CR20","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0304-3975(93)90126-E","volume":"115","author":"S. Homer","year":"1993","unstructured":"Homer, S., Kurtz, S., Royer, J.: A note on many-one and 1-truth table complete sets. Theor. Comput. Sci. 115(2), 383\u2013389 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"9163_CR21","first-page":"336","volume-title":"24th Conference on Foundations of Software Technology and Theoretical Computer Science","author":"J.M. Hitchcock","year":"2004","unstructured":"Hitchcock, J.M., Pavan, A.: Hardness hypotheses, derandomization, and circuit complexity. In: 24th Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 336\u2013347. Springer, Berlin (2004)"},{"key":"9163_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/11786986_41","volume-title":"ICALP (1)","author":"J.M. Hitchcock","year":"2006","unstructured":"Hitchcock, J.M., Pavan, A.: Comparing reductions to NP-complete sets. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP (1). Lecture Notes in Computer Science, vol. 4051, pp. 465\u2013476. Springer, Berlin (2006)"},{"issue":"2","key":"9163_CR23","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0022-0000(92)90023-C","volume":"44","author":"S. Homer","year":"1992","unstructured":"Homer, S., Selman, A.L.: Oracles for structural properties: the isomorphism problem and public-key cryptography. J. Comput. Syst. Sci. 44(2), 287\u2013301 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"9163_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3544-4","volume-title":"Computability and Complexity Theory","author":"S. Homer","year":"2001","unstructured":"Homer, S., Selman, A.L.: Computability and Complexity Theory. Springer, New York (2001)"},{"key":"9163_CR25","doi-asserted-by":"crossref","unstructured":"Kurtz, S., Mahaney, S., Royer, J.: The isomorphism conjecture fails relative to a random oracle. In Proc. 21nd Annual ACM Symposium on Theory of Computing, pp. 157\u2013166 (1989)","DOI":"10.1145\/73007.73022"},{"key":"9163_CR26","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. Krentel","year":"1988","unstructured":"Krentel, M.: The complexity of optimization problem. J. Comput. Syst. Sci. 36, 490\u2013509 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9163_CR27","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. Ladner","year":"1975","unstructured":"Ladner, R., Lynch, N., Selman, A.: A comparison of polynomial time reducibilities. Theor. Comput. Sci. 1, 103\u2013123 (1975)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9163_CR28","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1016\/0304-3975(94)00023-C","volume":"136","author":"E. Mayordomo","year":"1994","unstructured":"Mayordomo, E.: Almost every set in exponential time is p-bi-immune. Theor. Comput. Sci. 136(2), 487\u2013506 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"9163_CR29","unstructured":"Ronneburger, D.: Kolmogorov complexity and derandomization. PhD thesis, Rutgers University, New Brunswick, NJ, October 2004"},{"key":"9163_CR30","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(87)90132-0","volume":"54","author":"O. Watanabe","year":"1987","unstructured":"Watanabe, O.: A comparison of polynomial time completeness notions. Theor. Comput. Sci. 54, 249\u2013265 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"9163_CR31","first-page":"108","volume-title":"Complexity Theory Retrospective","author":"P. Young","year":"1990","unstructured":"Young, P.: Juris Hartmanis: Fundamental contributions to the isomorphism problems. In: Selman, A.L. (ed.) Complexity Theory Retrospective, pp. 108\u2013146. Springer, Berlin (1990)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9163-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T03:41:26Z","timestamp":1558064486000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9163-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,9]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["9163"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9163-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,9]]}}}