Immunity and simplicity in relativizations of probabilistic complexity classes

 Access to full text

 Full (PDF)

1. 1. L. ADLEMAN and K. MANDERS, Reducibility, Randomness, and Intractability, Proc. 9th A.C.M. Symp. Theory of Computing, 1977, pp. 151-163. MR502222
2. 2. T. BAKER, J. GILL and R. SOLOVAY, Relativizations of the P=? NP question, S.I.A.M. J. Computing, Vol. 4, 1975, pp. 431-442. Zbl0323.68033MR395311
3. 3. J. L. BALCÁZAR, Simplicity, Relativizations and Nondeterminism, S.I.A.M. J. Computing, Vol. 14, 1985, pp. 148-157. Zbl0567.68027MR774935
4. 4. J. GESKE and J. GROLLMAN, Relativizations of Unambiguous and Random Polynomial Time Classes, S.I.A.M. J. Computing, Vol. 15, 1986, pp. 511-519. Zbl0609.68038MR837599
5. 5. J. GILL, Computational Complexity of Probabilistic Turing Machines, S.I.A.M. J. Computing, Vol. 6, 1977; pp. 675-695. Zbl0366.02024MR464691
6. 6. Ph. FLAJOLET and J. M. STEYAERT, Une généralization de la notion d'ensemble immune, R.A.I.R.O., Vol. 8, R-l, 1974, pp. 37-48. Zbl0283.02034MR349364
7. 7. S. HOMER and W. MAASS, Oracle Dependent Properties of the Lattice of NP Sets, Theoret. Comput. Sci., Vol. 24, 1983, pp. 279-289. Zbl0543.03024MR716824
8. 8. J. E. HOPCROF and J. D. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. Zbl0426.68001MR645539
9. 9. Ch. RACKOFF, Relativized Questions Involving Probabilistic Algorithms, Proc. 10th A.C.M. Symp. Theory of Computing, 1978, pp. 338-342. Zbl1282.68158MR521067
10. 10. Ch. RACKOFF, Relativized Questions Involving Probabilistic Algorithms, J. Assoc. Comput. Math., Vol. 29, 1982, pp. 261-268. Zbl0477.68037MR662622
11. 11. D. A. Russo and S. ZACHOS, Positive Relativizations of Probabilistic Polynomial Time, Submitted for publication. 
12. 12. U. SCHÖNING, Complexity and Structure, Lecture Notes in Computer Science, Vol. 211, Springer-Verlag, 1986. Zbl0589.03022MR827009
13. 13. U. SCHÖNING and R. BOOK, Immunity, Relativizations, and Nondeterminism, S.I.A.M. J. Computing, Vol. 13, 1984, pp. 329-337. Zbl0558.68039MR739993
14. 14. L. VALIANT, Relative Complexity of Checking and Evaluating, Inf. Proc. Letters Vol. 5, 1976, pp. 20-23. Zbl0342.68028MR403318
15. 15. S. ZACHOS, Probabilistic Quantifiers, Adversaries, and Complexity Classes: an Overview, Proc. Conference on Structure in Complexity Theory, Lecture Notes in Computer Science, Vol. 223, Springer-Verlag, 1986, pp. 383-400. Zbl0632.03035MR854910

1. Ker-I Ko, A note on separating the relativized polynomial time hierarchy by immune sets
2. J. Rothe, Immunity and simplicity for exact counting and other counting classes
3. J. Rothe, Immunity and Simplicity for Exact Counting and Other Counting Classes