Probability one separation of the Boolean hierarchy
- 31 January 2006
- book chapter
- Published by Springer Nature
- p. 148-158
- https://doi.org/10.1007/bfb0039602
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchyPublished by Association for Computing Machinery (ACM) ,1986
- More complicated questions about maxima and minima, and some closures of NPPublished by Springer Nature ,1986
- The boolean hierarchy: Hardware over NPPublished by Springer Nature ,1986
- Randomness, relativizations, and polynomial reducibilitiesPublished by Springer Nature ,1986
- Separating the polynomial-time hierarchy by oraclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- The complexity of facets resolvedPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Relativized polynomial hierarchies extending two levelsTheory of Computing Systems, 1984
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse SetsSIAM Journal on Computing, 1983
- On the random oracle hypothesisPublished by Association for Computing Machinery (ACM) ,1982
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981