Sparse sets, tally sets, and polynomial reducibilities

1. E. Allender and R. Rubinstein, P-printable sets, SIAM J. Comput., to appear.

   Google Scholar 

2. E. Allender and O. Watanabe, Kolmogorov complexity and degrees of tally sets, Proc. 3rd IEEE Conf. Structure in Complexity Theory, 1988, to appear.

   Google Scholar 

3. K. Ambos-Spies, Randomness, relativizations and polynomial reducibilities, Proc. 1st Conf. Structure in Complexity Theory, LNCS 223, 1986, 23–34.

   Google Scholar 

4. A. Amir and W. Gasarch, Polynomial terse sets, Proc. 2nd IEEE Conf. Structure in Complexity Theory, 1987, 22–27.

   Google Scholar 

5. L. Babai, Trading group theory for randomness, Proc. 17th ACM Symp. Theory of Computing, 1985, 421–429.

   Google Scholar 

6. J. Balcázar and R. Book, Sets with small generalized Kolmogorov complexity, Acta Informatica 23 (1986), 679–688.

   Google Scholar 

7. J. Balcázar, R. Book, and U. Schöning, The polynomial-time hierarchy and sparse oracles, J. Assoc. Comput. Mach. 33 (1986), 603–617.

   Google Scholar 

8. J. Balcázar, J. Díaz, and J. Gabarró, Structural Complexity I, Springer-Verlag, 1988.

   Google Scholar 

9. R. Beigel, A structural theorem that depends quantitatively on the complexity of SAT, Proc. 2nd IEEE Conf. Structure in Complexity Theory, 1987, 28–32.

   Google Scholar 

10. C. Bennett and J. Gill, Relative to a random oracle, P ^A ≠ N P ^A ≠ co − N P ^A with probability 1, SIAM J. Comput. 10 (1981), 96–113.

    Google Scholar 

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

    Google Scholar 

12. P. Berman, Relationships between density and deterministic complexity of NP-complete languages, Automata, Languages and Programming — 78, LNCS 62, 1978, 63–71.

    Google Scholar 

13. R. Book, Bounded query machines: on NP and PSPACE, Theoret. Comput. Sci. 15 (1981), 27–39.

    Google Scholar 

14. R. Book and K. Ko, On sets truth-table reducible to sparse sets, SIAM J. Comput. 17 (1988), to appear. Also see Proc. 2nd IEEE Conf. Structure in Complexity Theory 1987, 147–155.

    Google Scholar 

15. R. Book and C. Wrathall, Bounded query machines: on NP() and NPQUERY(), Theoret. Comput. Sci. 15 (1981), 41–50.

    Google Scholar 

16. R. Book, P. Orponen, D. Russo, and O. Watanabe, Lowness properties in the exponent-time hierarcy, SIAM J. Comput. 17 (1988), to appear.

    Google Scholar 

17. S. Fortune, A note on sparse complete sets, SIAM J. Comput. 8 (1979), 431–433.

    Google Scholar 

18. S. Goldwasser and M. Sipser, Private coins in interactive proof systems, Proc. 18th ACM Symp. Theory of Computing 1986, 59–68.

    Google Scholar 

19. J. Hartmanis, Generalized Kolmogorov complexity and the structure of feasible computations, Proc. 24th IEEE Symp. Foundations of Computer Science 1983, 439–445.

    Google Scholar 

20. J. Hartmanis and L. Hemachandra, On sparse oracles separating feasible complexity classes, STACS-86, LNCS 210, 1986, 321–333.

    Google Scholar 

21. R. Karp and R. Lipton, Some connections between nonuniform and uniform complexity classes, Proc. 12th ACM Symp. Theory of Computing 1980, 302–309.

    Google Scholar 

22. K. Ko, Continuous optimization problems and a polynomial hierarchy of real functions, J. Complexity 1 (1985), 210–231.

    Google Scholar 

23. K. Ko, On the notion of infinite pseudo random sequences, Theoret. Comput. Sci. 48 (1988), 9–33.

    Google Scholar 

24. K. Ko, Distinguishing reducibilities by sparse sets, Proc. 3rd IEEE Conf. Structure in Complexity Theory, 1988, to appear.

    Google Scholar 

25. R. Ladner, M. Lynch, and A. Selman, A comparison of polynomial-time reducibilities, Theoret. Comput. Sci. 1 (1975), 103–123.

    Google Scholar 

26. M. Li and P. Vitanyi, Two decades of applied Kolmogorov complexity, Proc. 3rd IEEE Conf. Structure in Complexity Theory, 1988, to appear.

    Google Scholar 

27. T. Long, On restricting the size of oracles compared with restricting access to oracles, SIAM J. Comput. 14 (1985), 585–597.

    Google Scholar 

28. T. Long and A. Selman, Relativizing complexity classes with sparse oracles, J. Assoc. Comput. Mach. 33 (1988), 618–627.

    Google Scholar 

29. S. Mahaney, Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, J. Comput. Syst. Sci. 23 (1982), 130–143.

    Google Scholar 

30. N. Pippenger, On simultaneous resource bounds, Proc., 20th IEEE Symp. Foundations of Computer Science, 1979, 307–311.

    Google Scholar 

31. U. Schöning, Complexity and Structure, LNCS 211, 1986.

    Google Scholar 

32. U. Schöning, Complete sets and closeness to complexity classes, Math. Syst. Theory 19 (1986), 29–41.

    Google Scholar 

33. U. Schöning, Probabilistic complexity classes and lowness, Proc. 2nd IEEE Conf. Structure in Complexity Theory 1987, 2–8.

    Google Scholar 

34. M. Sipser, A complexity theory approach to randomness, Proc. 15th ACM Symp. Theory of Computing 1983, 330–335.

    Google Scholar 

35. S. Tang and R. Book, Separating polynomial-time Turing and truth-table reducibilities by tally sets, Automata, Languages and Programming-88, LNCS, 1988, to appear.

    Google Scholar 

36. S. Tang and R. Book, in preparation.

    Google Scholar 

37. S. Tang and O. Watanabe, On tally relativizations of BP-complexity classes, Proc. 3rd IEEE Conf. Structure in Complexity Theory, 1988, to appear.

    Google Scholar 

Download references