Immunity and simplicity in relativizations of probabilistic complexity classes
Balcázar, José L. ; Russo, David A.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988), p. 227-244 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@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},
     volume = {22},
     year = {1988},
     pages = {227-244},
     mrnumber = {951339},
     zbl = {0647.68053},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 227-244. http://gdmltest.u-ga.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 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. | 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