Ker-I Ko
- 1.D. Angluin, On counting problems and the polynomial time hierarchy, Theoret. Cornput. Sci. 12 (1980), 161-173.Google Scholar
Cross Ref
- 2.T. Baker, J. Gill and R. Solovay, Relativizations of the P-?NP question, SIAM J. comput. 4 (1975), 431-442.Google Scholar
- 3.T. Baker and A. Selman, A second step toward the polynomial llierarchy, Theoret. Cornpnt. ScJ. 8 (1979), t77-187.Google Scholar
- 4.M. Furst, J. Saxe and M. Sipser, Parity, circuits, and the polynomial time hierarchy, Math. Systems Theory 17 (1984), 13-27.Google ScholarCross Ref
- 5.J. T. Hastad, Computational Limitations/'or Sma//- Depth Circuits, (Ph.D. Dissertation, MIT), MIT Press, Cambridge, 1987. Google ScholarDigital Library
- 6.J. T. Hastad, Almost optimal lower bounds for small depth circuits, Proc. of ISth A(TM Syrup. a, Theory of C. oml~uting (1986), 6-20. Google ScholarDigital Library
- 7.H. Heller, Relativizcd polynolnial hierarchies extending two levels, Math. systems Theory 17 (19s4), 7~-s4.Google Scholar
- 8.J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. Google ScholarDigital Library
- 9.M. Sipser, Borel sets and circuit complexity, Proc. of 15th A CM Syrup. on Theory of Computing (10s3), 61-69. Google ScholarDigital Library
- 10.L. Stockmeyer, The polynomial-time hierarchy, Theoret. Comput. Sei. 3 (1977), 1--22.Google ScholarCross Ref
- 11.C. Wrathatl, Co,nplcte sets and the 1)olyno,nial hicrarclly, 'l'!tc~rct. (5~nll~,tt. Sci. 3 (1977), 23-33.Google Scholar
- 12.A. Yao, Separating the l~olyJ,t, tldal~tilne iticrarchy by oracles, l~ro~, ot' 26th IEEE $~vn,t,. ~,, l, bundations of Computer Science (1985), t 10. Google ScholarDigital Library
Index Terms
- Relativized polynomial time hierarchies having exactly K levels
Recommendations
Collapsing recursive oracles for relativized polynomial hierarchies
FCT'05: Proceedings of the 15th international conference on Fundamentals of Computation TheoryCertain recursive oracles can force the polynomial hierarchy to collapse to any fixed level. All collections of such oracles associated with each collapsing level form an infinite hierarchy, called the collapsing recursive oracle polynomial (CROP) ...
Comments