Sparse oracles, lowness, and highness

1. L. Adleman, Two theorems on random polynomial time. Proc. 19th IEEE Symp. Foundations of Computer Science (1978), 75–83.

   Google Scholar 

2. T. Baker, J. Gill, and R. Solovay, Relativizations of the P = ? NP question. SIAM J. Computing 4 (1975), 161–173.

   Google Scholar 

3. T. Baker and A. Selman, A second step towards the polynomial-time hierarchy. Theoret. Comput. Sci. 8 (1979), 177–187.

   Google Scholar 

4. P. Berman, Relationships between density and deterministic complexity of NP-complete languages. Proc. 5th ICALP, Lecture Notes in Computer Science 67 (1978), 63–71.

   Google Scholar 

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

   Google Scholar 

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

   Google Scholar 

7. 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 

8. K. Ko, On self-reducibility and weak P-selectivity. J. Comput. Syst. Sci. 26 (1982), 209–221.

   Google Scholar 

9. K. Ko and U. Schöning, On circuit-size complexity and the low hierarchy in NP. SIAM J. Computing 13 (1984), to appear.

   Google Scholar 

10. T. Long, A note on sparse oracles for NP. J. Comput. Syst. Sci. 24 (1982), 224–232.

    Google Scholar 

11. T. Long, Strong nondeterministic polynomial-time reducibilities. Theoret. Comput. Sci. 21 (1982), 1–25.

    Google Scholar 

12. T. Long and A. Selman, Relativizing complexity classes with sparse oracles. Unpublished abstract, June 1983.

    Google Scholar 

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

    Google Scholar 

14. A. Meyer and M. Paterson, With what frequency are apparently intractable problems difficult? M.I.T. Technical Report, Feb. 1979.

    Google Scholar 

15. U. Schöning, A low-and a high-hierarchy in NP. J. Comput. Syst. Sci. 27 (1983), 14–28.

    Google Scholar 

16. U. Schöning, A note on small generators. Submitted for publication.

    Google Scholar 

17. L. Stockmeyer, The polynomial-time hierarchy. Theoret. Comput. Sci. 3 (1976), 1–22.

    Google Scholar 

18. C. Wrathall, Complete sets and the polynomial-time hierarchy. Theoret. Comput. Sci. 3 (1976), 23–33.

    Google Scholar 

19. C. Yap, Some consequences of non-uniform conditions on uniform classes. Theoret. Comput. Sci. 27 (1984), 287–300.

    Google Scholar 

Download references