Separating the polynomial-time hierarchy by oracles
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 1-10
- https://doi.org/10.1109/sfcs.1985.49
Abstract
We present exponential lower bounds on the size of depth-k Boolean circuits for computing certain functions. These results imply that there exists an oracle set A such that, relative to A, all the levels in the polynomial-time hierarchy are distinct, i.e., ΣkP,A is properly contained in Σk+1P,A for all k.Keywords
This publication has 17 references indexed in Scilit:
- On monotone formulae with restricted depthPublished by Association for Computing Machinery (ACM) ,1984
- Lower bounds by probabilistic argumentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Languages which capture complexity classesPublished by Association for Computing Machinery (ACM) ,1983
- Exponential lower bounds for restricted monotone circuitsPublished by Association for Computing Machinery (ACM) ,1983
- Borel sets and circuit complexityPublished by Association for Computing Machinery (ACM) ,1983
- A second step toward the polynomial hierarchyTheoretical Computer Science, 1979
- Relativized questions involving probabilistic algorithmsPublished by Association for Computing Machinery (ACM) ,1978
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- The equivalence problem for regular expressions with squaring requires exponential spacePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1972