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

Voir la notice de l'article provenant de la source Numdam

@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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, Tome 22 (1988) no. 2, pp. 227-244. http://geodesic.mathdoc.fr/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. | Zbl | MR

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

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

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

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. | mathdoc-id | Zbl | MR | EuDML

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

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

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

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

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

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

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