In Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide, An oracle builder’s toolkit, Inf. Comput. 182, No. 2, 95-136 (2003). ZBL1025.68041, the authors go through a variety of generic oracles.

The top answer to the following question mentions that generic oracles tend to not be recursive, but can be made recursive. How does one go about making such a change? Does the technique generalize to all types of X-generic oracles? I'm particularly interested in making sp-generic oracles recursive, but I'm interested in other types of genericity as well.


I think the point is that every notion of genericity has uncountably many generic oracles in it (see, e.g., Fenner-Fortnow-Kurtz-Li Lemma 3.12), but there are only countably many computable sets, so most generic sets are uncomputable.

However, if you go back to the proof that a given set of conditions was generic, and that it was strong enough to force the things you wanted it to force to build the oracle you wanted, you can often use that proof more directly to actually construct a particular oracle. And such oracles are often easily shown to be computable (though I suppose there are surely situations where they just aren't computable, but that seems less common to me).

A good exercise is to consider what a "generics" proof of Baker-Gill-Solovay looks like. One way is as follows. Define a condition $\sigma$ (i.e. partial function $\Sigma^* \to \{0,1\}$ to be a $\mathcal{BGS}$ condition if it contains at most one string of each length, and if $x \in dom(\sigma)$ and $|x|=|y|$, then $y \in dom(\sigma)$. Show that this is a notion of genericity, so $\mathcal{BGS}$-generics exist, and show that it is strong enough to force the condition that the $n$-th polytime Turing machine disagrees with the language $L^G = \{1^n : (\exists x \in G)[|x|=n]\} \in \mathsf{NP}^G$.

Now look at your proof of the latter, and see how it is basically the same as BGS. But BGS just did it directly, and from the direct proof it's not hard to see that it's computable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.