Generic oracles and oracle classes
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 118-126
- https://doi.org/10.1109/sfcs.1987.30
Abstract
In this paper, we examine various complexity issues relative to an oracle for a generic set in order to determine which are the more "natural" conjectures for these issues. Generic oracle results should be viewed as parallels to random oracle results, as in [BG]; the two are in many ways related, but, as we shall exhibit, not equivalent. Looking at computation relative to a generic oracle is in some ways a better reflection of computation without an oracle; for example, whereas adding a random oracle allows a deterministic polynomial-time machine to solve any problem in BPP, adding a generic oracle will not help solve any recursive problem faster than it could be solved without an oracle. Generic sets were first introduced by Cohen as a tool for proving independence results in set theory [Co]. Their recursion theoretic properties have also been explored in depth; for example, see [J] and [Ku2]. Some related work using forcing and/or generic sets as tools in oracle constructions can be found in [Ku3], [Do], [P], and [A-SFH]. However, this is to our knowledge the first knowledge the first thorough examination of complexity relative to a generic Oracle.Keywords
This publication has 12 references indexed in Scilit:
- Random oracles separate PSPACE from the polynomial-time hierarchyInformation Processing Letters, 1987
- Complexity classes without machines: On complete languages for UPPublished by Springer Nature ,1986
- The boolean hierarchy: Hardware over NPPublished by Springer Nature ,1986
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchyPublished by Springer Nature ,1986
- Sparse Sets in : RelativizationsSIAM Journal on Computing, 1985
- Notions of weak genericityThe Journal of Symbolic Logic, 1983
- 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
- Degrees of Generic SetsPublished by Cambridge University Press (CUP) ,1980
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- THE INDEPENDENCE OF THE CONTINUUM HYPOTHESISProceedings of the National Academy of Sciences, 1963