Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 22, Number 2, 1988
Page(s) 227 - 244
DOI https://doi.org/10.1051/ita/1988220202271
Published online 01 February 2017
  1. 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. 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. 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. 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. 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. 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] [MR: 349364] [Zbl: 0283.02034]
  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. [MR: 716824] [Zbl: 0543.03024]
  8. 8. J. E. HOPCROF and J. D. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. [MR: 645539] [Zbl: 0426.68001]
  9. 9. Ch. RACKOFF, Relativized Questions Involving Probabilistic Algorithms, Proc. 10th A.C.M. Symp. Theory of Computing, 1978, pp. 338-342. [Zbl: 1282.68158] [MR: 521067]
  10. 10. Ch. RACKOFF, Relativized Questions Involving Probabilistic Algorithms, J. Assoc. Comput. Math., Vol. 29, 1982, pp. 261-268. [MR: 662622] [Zbl: 0477.68037]
  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. [MR: 827009] [Zbl: 0589.03022]
  13. 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. 14. L. VALIANT, Relative Complexity of Checking and Evaluating, Inf. Proc. Letters Vol. 5, 1976, pp. 20-23. [MR: 403318] [Zbl: 0342.68028]
  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. [MR: 854910] [Zbl: 0632.03035]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.