On exponential lowness

1. J. Balcázar and R. Book, On generalized Kolmogorov complexity, STACS 86, to appear.

   Google Scholar 

2. J. Balcázar, R. Book, and U. Schöning, Sparse oracles, lowness, and highness, SIAM J. Computing 16 (1986), to appear.

   Google Scholar 

3. R. Book, Tally languages and complexity classes, Info. & Control 26 (1974), 186–193.

   Google Scholar 

4. A. Chandra, D. Kozen, and L. Stockmeyer, Alternation, J. Assoc. Comput. Mach. 28 (1981), 114–133.

   Google Scholar 

5. M. Dekhtyar, On the relation of deterministic and nondeterministic complexity classes, Math. Found. Comput. Sci., Lecture Notes in Computer Science 45 (1977), Springer-Verlag, 282–287.

   Google Scholar 

6. A. Goldberg and M. Sipser, Compression and ranking, Proc. 17 ^th ACM Sym. Theory of Computing 1985, 440–448.

   Google Scholar 

7. J. Hartmanis, On aparse sets in NP-P, Info. Proc. Letters 16 (1983), 55–60.

   Google Scholar 

8. J. Hartmanis, Generalized Kolmogorov complexity and the structure of feasible computations, Proc. 24 ^thIEEE Sump. Foundations of Computer Science (1983), 439–445.

   Google Scholar 

9. J. Hartmanis, V. Sewelson, and N. Immerman, Sparse sets in NP-P: EXPTIME versus NEXPTIME, Proc. 15 ^th ACM Symp. Theory of Computing (1983), 382–391.

   Google Scholar 

10. H. Heller, On relativized polynomial and exponential computations, SIAM J. Computing 13 (1984), 717–725.

    Google Scholar 

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

    Google Scholar 

12. K. Ko and U. Schöning, On circuit-size complexity and the low hierarchy in NP, SIAM J. Computing 14 (1985), 41–51.

    Google Scholar 

13. P. Orponen, Complexity class of alternating machines with oracles, Automata. Languages, and Programming, Lecture Notes in Computer Science 154 (1983), Springer-Verlag, 573–584.

    Google Scholar 

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

    Google Scholar 

15. J. Simon, On Some Central Probems in Computational Complexity, Ph.D. dissertation, Cornell University, 1975.

    Google Scholar 

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

    Google Scholar 

17. C. Wilson, Relativization, Reducibilities, and the Exponential Hierarachy, M. Sc. thesis, Univ. of Toronto, 1980.

    Google Scholar 

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

    Google Scholar 

Download references