Lower bounds for the low hierarchy
Open Access
- 2 January 1992
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 39 (1) , 234-251
Abstract
No abstract availableThis publication has 21 references indexed in Scilit:
- Bounded queries to SAT and the Boolean hierarchyTheoretical Computer Science, 1991
- Kolmogorov complexity and degrees of tally setsInformation and Computation, 1990
- On Sets Truth-Table Reducible to Sparse SetsSIAM Journal on Computing, 1988
- Polynomial terse setsInformation and Computation, 1988
- Non-uniform proof systems: A new framework to describe non-uniform and probabilistic complexity classes1988
- Sets with small generalized Kolmogorov complexityActa Informatica, 1986
- Sparse Sets, Lowness and HighnessSIAM Journal on Computing, 1986
- A second step toward the polynomial hierarchyTheoretical Computer Science, 1979
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- Tally languages and complexity classesInformation and Control, 1974