Immunity and simplicity in relativizations of probabilistic complexity classes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988) no. 2, pp. 227-244.
@article{ITA_1988__22_2_227_0,
     author = {Balc\'azar, Jos\'e L. and Russo, David A.},
     title = {Immunity and simplicity in relativizations of probabilistic complexity classes},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {227--244},
     publisher = {EDP-Sciences},
     volume = {22},
     number = {2},
     year = {1988},
     zbl = {0647.68053},
     mrnumber = {951339},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1988__22_2_227_0/}
}
TY  - JOUR
AU  - Balcázar, José L.
AU  - Russo, David A.
TI  - Immunity and simplicity in relativizations of probabilistic complexity classes
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1988
DA  - 1988///
SP  - 227
EP  - 244
VL  - 22
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1988__22_2_227_0/
UR  - https://zbmath.org/?q=an%3A0647.68053
UR  - https://www.ams.org/mathscinet-getitem?mr=951339
LA  - en
ID  - ITA_1988__22_2_227_0
ER  - 
Balcázar, José L.; Russo, David A. Immunity and simplicity in relativizations of probabilistic complexity classes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988) no. 2, pp. 227-244. http://www.numdam.org/item/ITA_1988__22_2_227_0/

1. L. Adleman and K. Manders, Reducibility, Randomness, and Intractability, Proc. 9th A.C.M. Symp. Theory of Computing, 1977, pp. 151-163. | MR 502222

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. | MR 395311 | Zbl 0323.68033

3. J. L. Balcázar, Simplicity, Relativizations and Nondeterminism, S.I.A.M. J. Computing, Vol. 14, 1985, pp. 148-157. | MR 774935 | Zbl 0567.68027

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. | MR 837599 | Zbl 0609.68038

5. J. Gill, Computational Complexity of Probabilistic Turing Machines, S.I.A.M. J. Computing, Vol. 6, 1977; pp. 675-695. | MR 464691 | Zbl 0366.02024

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. | EuDML 92004 | Numdam | MR 349364 | Zbl 0283.02034

7. S. Homer and W. Maass, Oracle Dependent Properties of the Lattice of NP Sets, Theoret. Comput. Sci., Vol. 24, 1983, pp. 279-289. | MR 716824 | Zbl 0543.03024

8. J. E. Hopcrof and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. | MR 645539 | Zbl 0426.68001

9. Ch. Rackoff, Relativized Questions Involving Probabilistic Algorithms, Proc. 10th A.C.M. Symp. Theory of Computing, 1978, pp. 338-342. | MR 521067 | Zbl 1282.68158

10. Ch. Rackoff, Relativized Questions Involving Probabilistic Algorithms, J. Assoc. Comput. Math., Vol. 29, 1982, pp. 261-268. | MR 662622 | Zbl 0477.68037

11. D. A. Russo and S. Zachos, Positive Relativizations of Probabilistic Polynomial Time, Submitted for publication.

12. U. Schöning, Complexity and Structure, Lecture Notes in Computer Science, Vol. 211, Springer-Verlag, 1986. | MR 827009 | Zbl 0589.03022

13. U. Schöning and R. Book, Immunity, Relativizations, and Nondeterminism, S.I.A.M. J. Computing, Vol. 13, 1984, pp. 329-337. | MR 739993 | Zbl 0558.68039

14. L. Valiant, Relative Complexity of Checking and Evaluating, Inf. Proc. Letters Vol. 5, 1976, pp. 20-23. | MR 403318 | Zbl 0342.68028

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. | MR 854910 | Zbl 0632.03035