×

Immunity and simplicity in relativizations of probabilistic complexity classes. (English) Zbl 0647.68053

A set A is immune for a complexity class C if every subset of A in C is finite. The notion of simplicity is somewhat dual to immunity. In this paper it is shown that in certain “relativized worlds” (i.e. with respect to some oracle set) there exist simple or immune sets for several probabilistic complexity classes. The proofs are stage-by-stage diagonalization constructions. Typical for probabilistic complexity classes is that certain “critical string control” techniques are needed.
Reviewer: U.Schöning

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)

References:

[1] 1. L. ADLEMAN and K. MANDERS, Reducibility, Randomness, and Intractability, Proc. 9th A.C.M. Symp. Theory of Computing, 1977, pp. 151-163. MR502222
[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. Zbl0323.68033 MR395311 · Zbl 0323.68033 · doi:10.1137/0204037
[3] 3. J. L. BALCÁZAR, Simplicity, Relativizations and Nondeterminism, S.I.A.M. J. Computing, Vol. 14, 1985, pp. 148-157. Zbl0567.68027 MR774935 · Zbl 0567.68027 · doi:10.1137/0214012
[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. Zbl0609.68038 MR837599 · Zbl 0609.68038 · doi:10.1137/0215035
[5] 5. J. GILL, Computational Complexity of Probabilistic Turing Machines, S.I.A.M. J. Computing, Vol. 6, 1977; pp. 675-695. Zbl0366.02024 MR464691 · Zbl 0366.02024 · doi:10.1137/0206049
[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. Zbl0283.02034 MR349364 · 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. Zbl0543.03024 MR716824 · Zbl 0543.03024 · doi:10.1016/0304-3975(83)90003-8
[8] 8. J. E. HOPCROF and J. D. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. Zbl0426.68001 MR645539 · 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. MR521067 · Zbl 1282.68158
[10] 10. Ch. RACKOFF, Relativized Questions Involving Probabilistic Algorithms, J. Assoc. Comput. Math., Vol. 29, 1982, pp. 261-268. Zbl0477.68037 MR662622 · Zbl 0477.68037 · doi:10.1145/322290.322306
[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. Zbl0589.03022 MR827009 · 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. Zbl0558.68039 MR739993 · Zbl 0558.68039 · doi:10.1137/0213023
[14] 14. L. VALIANT, Relative Complexity of Checking and Evaluating, Inf. Proc. Letters Vol. 5, 1976, pp. 20-23. Zbl0342.68028 MR403318 · Zbl 0342.68028 · doi:10.1016/0020-0190(76)90097-1
[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. Zbl0632.03035 MR854910 · Zbl 0632.03035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.