Non-Uniform Reductions

1. Agrawal, M.: Pseudo-random generators and structure of complete degrees. In IEEE Conference on Computational Complexity, pp. 139–147 (2002)

2. 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–80. IEEE Computer Society, Los Alamitos (1993)

   Google Scholar 

3. Allender, E.: Isomorphisms and 1-L reductions. J. Comput. Syst. Sci. 36(6), 336–350 (1988)

   Article  MATH  MathSciNet  Google Scholar 

4. Allender, E., Buhrman, H., Koucký, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. In: FOCS, pp. 669–678. IEEE Computer Society, Los Alamitos (2002)

   Google Scholar 

5. Ambos-Spies, K.: p-mitotic sets. In: Börger, E., Hasenjäger, G., Roding, D. (eds.) Logic and Machines. Lecture Notes in Computer Science, vol. 177, pp. 1–23. Springer, Berlin (1984)

   Google Scholar 

6. Balcázar, J., Díaz, J., Gabarró, J.: Structural Complexity I. Springer, Berlin (1988)

   MATH  Google Scholar 

7. Berman, L., Hartmanis, H.: On isomorphisms and density of NP and other complete sets. SIAM J. Comput. 6, 305–322 (1977)

   Article  MATH  MathSciNet  Google Scholar 

8. Buhrman, H., Mayordomo, E.: An excursion to the Kolmogorov random strings. In: Proceedings Structure in Complexity Theory, 10th Annual Conference (STRUCTURES95), Minneapolis, pp. 197–205. IEEE Computer Society, Los Alamitos (1995)

   Google Scholar 

9. Buhrman, H., Torenvliet, L.: Complicated complementations. In: Proceedings 14th IEE Conference on Computational Complexity, pp. 227–236. IEEE Computer Society, Los Alamitos (1999)

   Google Scholar 

10. Buhrman, H., Torenvliet, L.: Separating complexity classes using structural properties. In: Proceedings 19th IEE Conference on Computational Complexity, pp. 130–138. IEEE Computer Society, Los Alamitos (2004)

    Chapter  Google Scholar 

11. Buhrman, H., Torenvliet, L.: A Post’s program for complexity theory. In Bulletin of the EATCS 85, pp. 41–51 (2005)

12. Buhrman, H., Homer, S., Torenvliet, L.: On complete sets for nondeterministic classes. Math. Syst. Theory 24, 179–200 (1991)

    Article  MATH  MathSciNet  Google Scholar 

13. Buhrman, H., Spaan, E., Torenvliet, L.: Bounded reductions. In: Ambos-Spies, K., Homer, S., Schöning, U. (eds.) Complexity Theory, pp. 83–99. Cambridge University Press, Cambridge (1993)

    Google Scholar 

14. Buhrman, H., Spaan, E., Torenvliet, L.: The relative power of logspace and polynomial time reductions. Comput. Complexity 3(3), 231–244 (1993)

    Article  MATH  MathSciNet  Google Scholar 

15. Buhrman, H., van Melkebeek, D., Fortnow, L., Torenvliet, L.: Using autoreducibility to separate complexity classes. SIAM J. Comput. 29(5), 1497–1520 (2000)

    Article  MATH  MathSciNet  Google Scholar 

16. 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–39 (1992)

17. 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–250. Springer, Berlin (1988)

    Google Scholar 

18. Glaßer, 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–157. Springer, Berlin (2007)

    Google Scholar 

19. Hartmanis, J., Hemachandra, L.: One-way functions and the non-isomorphism of NP-complete sets. Theor. Comput. Sci. 81(1), 155–163 (1991)

    Article  MATH  MathSciNet  Google Scholar 

20. Homer, S., Kurtz, S., Royer, J.: A note on many-one and 1-truth table complete sets. Theor. Comput. Sci. 115(2), 383–389 (1993)

    Article  MATH  MathSciNet  Google Scholar 

21. 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–347. Springer, Berlin (2004)

    Chapter  Google Scholar 

22. 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–476. Springer, Berlin (2006)

    Google Scholar 

23. Homer, S., Selman, A.L.: Oracles for structural properties: the isomorphism problem and public-key cryptography. J. Comput. Syst. Sci. 44(2), 287–301 (1992)

    Article  MATH  MathSciNet  Google Scholar 

24. Homer, S., Selman, A.L.: Computability and Complexity Theory. Springer, New York (2001)

    MATH  Google Scholar 

25. 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–166 (1989)

26. Krentel, M.: The complexity of optimization problem. J. Comput. Syst. Sci. 36, 490–509 (1988)

    Article  MATH  MathSciNet  Google Scholar 

27. Ladner, R., Lynch, N., Selman, A.: A comparison of polynomial time reducibilities. Theor. Comput. Sci. 1, 103–123 (1975)

    Article  MATH  MathSciNet  Google Scholar 

28. Mayordomo, E.: Almost every set in exponential time is p-bi-immune. Theor. Comput. Sci. 136(2), 487–506 (1994)

    Article  MATH  MathSciNet  Google Scholar 

29. Ronneburger, D.: Kolmogorov complexity and derandomization. PhD thesis, Rutgers University, New Brunswick, NJ, October 2004

30. Watanabe, O.: A comparison of polynomial time completeness notions. Theor. Comput. Sci. 54, 249–265 (1987)

    Article  MATH  Google Scholar 

31. Young, P.: Juris Hartmanis: Fundamental contributions to the isomorphism problems. In: Selman, A.L. (ed.) Complexity Theory Retrospective, pp. 108–146. Springer, Berlin (1990)

    Google Scholar 

Download references