Relativization with Respect to Non-Recursive Oracles

Question

In the paper Relativizations of the P = ? NP Question, Baker et al. showed that there are relativized worlds in which either P = NP or P ≠ NP holds. All oracles in their settings were recursive sets.

In another paper Relative to a Random Oracle $A$, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability $1$, Bennett and Gill put forward the notion of random oracles, which are almost surely non-recursive sets. (See the comments below.)

I wasn't aware of any other non-recursive relativizations, unless I came up with one (see this question and Joshua's answer to it.)

What are the implications of non-recursive relativizations? How are they useful in structural complexity theory?

Answer 1

(1) Lance Fortnow and Scott Aaronson (Section 1.3) give good discussions about the role of oracles/relativization in general, and I believe most, if not all, of their comments remain valid whether or not the oracle is computable.

On the other hand, thinking of oracle separations as query complexity separations (one of the views in Aaronson's paper), a non-computable oracle gives a query complexity separation where the function being queried is non-computable, which means the function being queried probably didn't arise in the real world. Nonetheless, it still seems like a potentially good guide to research.

(2) From the point of view of the Arora, Impagliazzo, and Vazirani paper, I'd say that non-computable oracles are far far outside the realm of the "real world" of computation.

(3) If we think of the "computational world relative to an oracle" as simply another model of computation, then relative to a computable oracle the computable sets in this model are of course the same as the standard model, whereas relative to a non-computable oracle, there are "computable" sets that are not computable in the standard model. (This is completely trivial -- it's mostly a philosophical viewpoint.)

(4) In a similar manner to random oracles, generic oracles tend not to be computable, though I imagine many (but probably not all) generic oracle constructions can be adapted with very little work to get computable oracles from them. (There is in fact a notion of genericity $\mathcal{R}$ such that $\mathcal{R}$-generic oracle results are the same thing as random oracle results, so this is really a generalization of the observation about randoms.)

Answer 2

I can't resist putting in a plug for some recent results, indicating that it can be interesting to consider computation relative to the (non-computable) set of Kolmogorov-random strings.

Let $R$ be the set of Kolmogorov-random strings; that is, the set of strings $x$ such that $K(x)$ is greater than or equal to $|x|$. (Actually, each "optimal" prefix Turing machine $U$ gives a different version $R_U$ of this set; usually it doesn't make much difference which $U$ we use to define $K$; it affects $K(x)$ only by $O(1)$.)

Buhrman et al. showed (at CCC 2010) that $BPP$ is poly-time truth-table reducible to $R$, and earlier work showed that $PSPACE$ is in $P^R$, and NEXP is in $NP^R$.

These might seem like fairly worthless results, since they give a non-computable upper bound on complexity classes! However a recent paper (see http://www.eccc.uni-trier.de/report/2010/138/ ) shows $PSPACE$ is an upper bound on the class of decidable sets that are poly-time truth-table reducible to $R_U$ for every $U$. That is, $PSPACE$ is sandwiched between the class of decidable problems that are Turing and truth-table reducible to $R$.

The same paper also shows that Exponential Space is an upper bound on the class of decidable problems that are in $NP^{R_U}$ for every $U$. I would guess that it might be possible to characterize $NEXP$ in this way.