Immunity and simplicity in relativizations of probabilistic complexity classes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 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},
     mrnumber = {951339},
     zbl = {0647.68053},
     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
SP  - 227
EP  - 244
VL  - 22
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1988__22_2_227_0/
LA  - en
ID  - ITA_1988__22_2_227_0
ER  - 
%0 Journal Article
%A Balcázar, José L.
%A Russo, David A.
%T Immunity and simplicity in relativizations of probabilistic complexity classes
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1988
%P 227-244
%V 22
%N 2
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1988__22_2_227_0/
%G en
%F ITA_1988__22_2_227_0
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, Volume 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

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 | Zbl

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

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 | Zbl

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

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 | Numdam | MR | Zbl

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 | Zbl

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

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

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

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 | Zbl

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

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

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 | Zbl