Additional queries to random and pseudorandom oracles

1. A. Amir, R. Beigel, and W. I. Gasarch, Cheatable, p-terse, and p-superterse sets, Proceedings of the Fifth Structure in Complexity Theory Conference, 1990, to appear.

   Google Scholar 

2. R. V. Book and K. Ko, On sets truth-table reducible to sparse sets, SIAM Journal on Computing 17 (1988), pp. 903–919.

   Google Scholar 

3. G. J. Chaitin, A theory of program size formally identical to information theory, Journal of the Association for Computing Machinery 22 (1975), pp. 329–340.

   Google Scholar 

4. R. I. Freidzon, Families of recursive predicates of measure zero, translated in Journal of Soviet Mathematics 6 (1976), pp. 449–455, 1972.

   Google Scholar 

5. P. R. Halmos, Measure Theory, Springer-Verlag, 1950.

   Google Scholar 

6. R. E. Ladner, N. Lynch, and A. L. Selman, A comparison of polynomial-time reducibilities, Theoretical Computer Science 1 (1975), pp. 103–123.

   Google Scholar 

7. L. A. Levin, On the notion of a random sequence, Soviet Mathematics Doklady 14 (1973), pp. 1413–1416.

   Google Scholar 

8. J. H. Lutz, Resource-bounded category and measure in complexity classes, Ph.D. dissertation, California Institute of Technology, 1987. Also see, Category and measure in complexity classes, SIAM Journal on Computing, to appear.

   Google Scholar 

9. J. H. Lutz, Almost everywhere high nonuniform complexity, Proceedings of the Fourth Structure in Complexity Theory Conference, pp. 37–53, 1989.

   Google Scholar 

10. J. H. Lutz, Pseudorandom sources for BPP, Journal of Computer and System Sciences 40, 1990, to appear.

    Google Scholar 

11. P. Martin-Löf, On the definition of random sequences, Information and Control 9 (1966), pp. 602–619.

    Google Scholar 

12. K. Mehlhorn, The “almost all” theory of subrecursive degrees is decidable, Proceedings of the Second Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science (1974), pp. 317–325.

    Google Scholar 

13. C. P. Schnorr, Process complexity and effective random tests, Journal of Computer and System Sciences 7 (1973), pp. 376–388.

    Google Scholar 

14. S. Tang and R. V. Book, Polynomial-time reducibilities and “almost-all” oracle sets, Theoretical Computer Science, 1990, to appear.

    Google Scholar 

15. O. Watanabe, A comparison of polynomial time completeness notions, Theoretical Computer Science 54 (1987), pp. 249–265.

    Google Scholar 

Download references