Degrees of Dowd-Type Generic Oracles

摘要

For each positive integer r, M. Dowd (1992, Inform, and Comput. 96,65-76) introduced r-generic oracles (we call them r-Dowd oracles; they are different from n-genericity of arithmetical forcing). An oracle D is r-Dowd if every r-query tautology with respect to D is force by a pollynomial-sized portion of D. we propose the study of degrees and complexity of 1-Downd oracles. Dowd also stated that no r-Dowd oracle is recursively enumerable. However, this is false. We show, among others, the following.