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?

  • 1
    $\begingroup$ I don't understand what you mean by "random oracles, which are non-recursive sets." Do you mean that a random oracle is non-recursive with probability 1? $\endgroup$ Commented Sep 26, 2010 at 3:50
  • 1
    $\begingroup$ Yes. Random oracles are chosen randomly from the set of all functions. A countably infinite part of this set is recursive, while an uncountable part of the set is non-recursive. Thus, with probability 1, the random oracle defines a non-recursive function. $\endgroup$ Commented Sep 26, 2010 at 7:16

2 Answers 2


(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.)


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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