A note on separating the relativized polynomial time hierarchy by immune sets
Ko, Ker-I
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990), p. 229-240 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1990__24_3_229_0,
     author = {Ko, Ker-I},
     title = {A note on separating the relativized polynomial time hierarchy by immune sets},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {24},
     year = {1990},
     pages = {229-240},
     mrnumber = {1072992},
     zbl = {0701.68032},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1990__24_3_229_0}
}

Ko, Ker-I. A note on separating the relativized polynomial time hierarchy by immune sets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990) pp. 229-240. http://gdmltest.u-ga.fr/item/ITA_1990__24_3_229_0/

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

2. J. Balcázar, Simplicity, Relativizations, and Nondeterminism, S.I.A.M. J. Comput. Vol. 14, 1985, pp. 148-157. | MR 774935 | Zbl 0567.68027

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. | Numdam | MR 951339 | Zbl 0647.68053

4. J. Balcázar and U. Schöning, Bi-Immune Sets for Complexity Classes, Math. Systems Theory, Vol. 18, 1985, pp. 1-10. | MR 793007 | Zbl 0572.68035

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

6. M. Furst, J. Saxe and M. Sipser, Parity, Circuits and the Polynomial-Time Hierarchy, Math. Systems Theory, Vol. 17, 1984, pp. 13-27. | MR 738749 | Zbl 0534.94008

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

9. K. Ko, Nonlevelable Sets and Immune Sets in the Accepting Density Hierarchy in NP, Math. Systems Theory, Vol. 18, 1985, pp. 189-205. | MR 813643 | Zbl 0586.68043

10. K. Ko, Relativized Polynomial Time Hierarchies Having Exactly k Levels, S.I.A.M. J. Comput., Vol. 18, 1989, pp. 392-408. | MR 986675 | Zbl 0679.68088

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. | Zbl 0506.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. | MR 739993 | Zbl 0558.68039

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

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.