On oracle builder's toolkit
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 120-131
- https://doi.org/10.1109/sct.1993.336534
Abstract
It is shown how to use various notions of genericity as a tool in oracle creation. A general framework for defining different types of generic sets in terms of arithmetic forcing is given. A number of basic facts about Cohen generic sets, many of which are generalizations of known results, are systematically assembled. We define sp-generic sets and extend some previous results.Keywords
This publication has 14 references indexed in Scilit:
- On the degree of Boolean functions as real polynomialsPublished by Association for Computing Machinery (ACM) ,1992
- One-way functions and the nonisomorphism of NP-complete setsTheoretical Computer Science, 1991
- Decision trees and downward closuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Generic oracles and oracle classesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Degrees of Generic SetsPublished by Cambridge University Press (CUP) ,1980
- On the size of sets of computable functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1973
- Forcing with perfect closed setsProceedings of Symposia in Pure Mathematics, 1971
- THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS, IIProceedings of the National Academy of Sciences, 1964
- THE INDEPENDENCE OF THE CONTINUUM HYPOTHESISProceedings of the National Academy of Sciences, 1963
- On Degrees of Recursive UnsolvabilityAnnals of Mathematics, 1956