On generalized kolmogorov complexity

1. J. Balcázar, R. Book, and U. Schöning, On bounded query machines, Theoret. Comput. Sci., to appear.

   Google Scholar 

2. J. Balcázar, R. Book, and U. Schöning, Sparse sets, lowness, and highness, SIAM J. Computing, to appear. Also see Mathematical Foundations of Computer Science — 1984, Lecture Notes in Computer Science 176 (1984), 185–193.

   Google Scholar 

3. R. Book, T. Long, and A. Selman, Quantitative relativizations of complexity classes, SIAM J. Computing 13 (1984), 461–487.

   Article  Google Scholar 

4. G. Chaitin, On the length of programs for computing finite binary sequences, J. Assoc. Comput. Mach. 13 (1966), 547–569.

   Google Scholar 

5. G. Chaitin, Information-theoretic limitations of formal systems, J. Assoc. Comput. Mach. 21 (1974), 403–424.

   Google Scholar 

6. G. Chaitin, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach. 22 (1975), 329–340.

   Google Scholar 

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

   Google Scholar 

8. K. Ko, Resource-bounded program-size complexity and pseudo-random sequences, Technical Report, University of Houston.

   Google Scholar 

9. K. Ko, Continuous optimization problems and a polynomial hierarchy of real functions, J. Complexity, to appear.

   Google Scholar 

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

11. A. Kolmogorov, Three approaches for defining the concept of information quality, Prob. Info. Trans. 1 (1965), 1–7.

    Google Scholar 

12. R. Ladner, The circuit value problem is log space complete for P, SIGACT News 7 (1975), 18–20.

    Article  Google Scholar 

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

    Google Scholar 

14. T. Long and A. Selman, Relativizing complexity classes with sparse oracles, J. Assoc. Comput. Mach., to appear.

    Google Scholar 

15. W. Paul, J. Seiferas, and J. Simon, An information-theoretic approach to time bounds for on-line computation, Proc. 12th ACM Symp. Theory of Computing, 1980, 357–367.

    Google Scholar 

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

    Google Scholar 

17. U. Schöning, Habilitationsschrift, Institut für Informatik, Universität Stuttgart, 1985.

    Google Scholar 

18. A. Selman, Xu Mei-rui, and R. Book, Positive relativizations of complexity classes, SIAM J. Computing 12 (1983), 565–579.

    Google Scholar 

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

    Google Scholar 

Download references