<p>(1) <a href="http://www.cs.uchicago.edu/~fortnow/papers/relative.pdf" rel="nofollow">Lance Fortnow</a> and <a href="http://eccc.uni-trier.de/report/2009/104/" rel="nofollow">Scott Aaronson (Section 1.3)</a> 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.  </p>

<p>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.</p>

<p>(2) From the point of view of the <a href="http://cseweb.ucsd.edu/~russell/ias.ps" rel="nofollow">Arora, Impagliazzo, and Vazirani</a> paper, I'd say that non-computable oracles are far far outside the realm of the "real world" of computation.</p>

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

<p>(4) In a similar manner to random oracles, <a href="http://dx.doi.org/10.1016/S0890-5401(03)00018-X" rel="nofollow">generic oracles</a> 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.)</p>

CC BY-SA 2.5
2010-09-26T04:30:05.977Z
2010-09-29T00:08:54.807Z
2010-09-29T00:08:54.807Z
Joshua Grochow
<p>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.</p>

<p>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)$.)</p>

<p><a href="http://people.cs.uchicago.edu/~fortnow/papers/bppr.pdf">Buhrman <em>et al.</em></a> 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$.</p>

<p>These might seem like fairly worthless results, since they give a non-computable upper bound on complexity classes!  However a recent paper (see <a href="http://www.eccc.uni-trier.de/report/2010/138/">http://www.eccc.uni-trier.de/report/2010/138/</a> ) 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$.  </p>

<p>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 <em>characterize</em> $NEXP$ in this way.</p>

CC BY-SA 2.5
2010-11-22T10:49:40.540Z
I think Eric reference is wrong, I guess he meant to link this paper http://www.eccc.uni-trier.de/report/2010/139/ instead of http://www.eccc.uni-trier.de/report/2010/138/
Sebastian Ben Daniel
CC BY-SA 2.5
2010-09-28T10:22:12.210Z
2010-09-28T18:27:43.377Z
2010-09-28T18:27:43.377Z
Eric Allender
<p>In the paper <a href="http://dx.doi.org/10.1137/0204037" rel="nofollow noreferrer">Relativizations of the P = ? NP Question</a>, Baker <em>et al.</em> showed that there are relativized worlds in which either P = NP or P ≠ NP holds. All oracles in their settings were recursive sets.</p>

<p>In another paper <a href="http://dx.doi.org/10.1137/0210008" rel="nofollow noreferrer">Relative to a Random Oracle $A$, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability $1$</a>, Bennett and Gill put forward the notion of random oracles, which are <a href="http://en.wikipedia.org/wiki/Almost_surely" rel="nofollow noreferrer">almost surely</a> non-recursive sets. (See the comments below.)</p>

<p>I wasn't aware of any other non-recursive relativizations, unless I came up with one (see <a href="https://cstheory.stackexchange.com/q/1618/873">this question</a> and Joshua's answer to it.)</p>

<blockquote>
  <p>What are the implications of non-recursive relativizations? How are they useful in structural complexity theory?</p>
</blockquote>

CC BY-SA 2.5
2010-09-26T03:50:10.393Z
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?
Robin Kothari
CC BY-SA 2.5
2010-09-26T07:16:20.373Z
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.
Sadeq Dousti
<cc.complexity-theory><computability><oracles><relativization>
Relativization with Respect to Non-Recursive Oracles
Sadeq Dousti
# Relativization with Respect to Non-Recursive Oracles

(Asked by: username_0 on 2010-09-26)

In the paper [Relativizations of the P = ? NP Question](http://dx.doi.org/10.1137/0204037), 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$](http://dx.doi.org/10.1137/0210008), Bennett and Gill put forward the notion of random oracles, which are [almost surely](http://en.wikipedia.org/wiki/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](https://cstheory.stackexchange.com/q/1618/873) and Joshua's answer to it.)

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

**Tags:** cc.complexity-theory, computability, oracles, relativization

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_2 on 2010-09-26. Score: 8 | Accepted answer

(1) [Lance Fortnow](http://www.cs.uchicago.edu/~fortnow/papers/relative.pdf) and [Scott Aaronson (Section 1.3)](http://eccc.uni-trier.de/report/2009/104/) 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](http://cseweb.ucsd.edu/~russell/ias.ps) 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](http://dx.doi.org/10.1016/S0890-5401(03)00018-X) 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 by username_3 on 2010-09-28. Score: 14

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.*](http://people.cs.uchicago.edu/~fortnow/papers/bppr.pdf) 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.

> **Comments:**
> **username_4**: I think Eric reference is wrong, I guess he meant to link this paper http://www.eccc.uni-trier.de/report/2010/139/ instead of http://www.eccc.uni-trier.de/report/2010/138/  

---

