A note on separating the relativized polynomial time hierarchy by immune sets
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1990)
- Volume: 24, Issue: 3, page 229-240
- ISSN: 0988-3754
Access Full Article
topHow to cite
topReferences
top- 1. T. BAKER, J. GILL and R. SOLOVAY, Relativizations of the P=?NP Question, S.I.A.M. J. Comput, Vol. 4, 1975, pp. 431-442. Zbl0323.68033MR395311
- 2. J. BALCÁZAR, Simplicity, Relativizations, and Nondeterminism, S.I.A.M. J. Comput. Vol. 14, 1985, pp. 148-157. Zbl0567.68027MR774935
- 3. J. BALCÁZAR and D. Russo, Immunity and Simplicity in Relativizations of Probabilistic Complexity Classes, R.A.I.R.O. Theoretical Informaties and Applications, Vol. 22, 1988, pp. 227-244. Zbl0647.68053MR951339
- 4. J. BALCÁZAR and U. SCHÖNING, Bi-Immune Sets for Complexity Classes, Math. Systems Theory, Vol. 18, 1985, pp. 1-10. Zbl0572.68035MR793007
- 5. C. BENNETT and J. GILL, Relative to a Rondom Oracle A, PA≠NPA≠co-NPA with Probability1 S.I.A.M. J. Comput., Vol. 10, 1981, pp. 96-113. Zbl0454.68030MR605606
- 6. M. FURST, J. SAXE and M. SIPSER, Parity, Circuits and the Polynomial-Time Hierarchy, Math. Systems Theory, Vol. 17, 1984, pp. 13-27. Zbl0534.94008MR738749
- 7. J. HASTAD, Almost Optimal Lower Boundsfor Small Depth Circuits, Proc. 18th A.C.M. Symp. on Theory of Computing, 1986, pp. 71-84.
- 8. S. HOMER and W. MAASS, Oracle Dependent Properties of the Lattice of NP Sets, Theoret. Comput. Sci.,Vol. 24, 1983, pp.279-289. Zbl0543.03024MR716824
- 9. K. Ko, Nonlevelable Sets and Immune Sets in the Accepting Density Hierarchy in NP, Math. Systems Theory, Vol. 18, 1985, pp. 189-205. Zbl0586.68043MR813643
- 10. K. Ko, Relativized Polynomial Time Hierarchies Having Exactly k Levels, S.I.A.M. J. Comput., Vol. 18, 1989, pp. 392-408. Zbl0679.68088MR986675
- 11. C. PAPADIMITRIOU and S. ZACHOS, TWO Remarks on the Power of Counting, Proc. 6th GI Conf. on Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 145, 1983, pp. 269-276. Zbl0506.68039
- 12. D. RUSSO, Structural Properties of Complexity Classes, Ph. D. dissertation, University of California, Santa Barbara, 1985.
- 13. U. SCHÖNING and R. BOOK, Immunity, Relativizations and Nondeterminism, S.I.A.M. J. Comput., Vol. 13, 1984, pp. 329-337. Zbl0558.68039MR739993
- 14. L. TORENVLIET and P. VAN EMDE BOAS, Diagonalization Methods in a Polynomial Setting, Proc. Structure in Complexity Theory Conf., Lecture Notes in Computer Science, Vol.223, 1986, pp. 330-346. Zbl0611.68019MR854907
- 15. A. YAO, Separating the Polynomial-Time Hierarchy by Oracles, Proc. 26th I.E.E.E. Symp. on Foundations of Computer Science, 1985, pp. 1-10.