<p>There are several well known results regarding random oracles, e.g.</p>

<blockquote>
  <p>$\mathsf{IP}^A \neq \mathsf{PSpace}^A$ for almost all oracles. </p>
</blockquote>

<p>Are there any known natural examples where a similar statement is both true and false for significant fractions of the random oracles (e.g. it is true with probability $1/2$)?</p>

CC BY-SA 3.0
2012-09-18T09:12:53.077Z
No interesting result will depend on the oracle's values on a particular finite set, so this seems to be ruled out by Kolmogorov's zero-one law.
Colin McQuillan
CC BY-SA 3.0
2012-09-18T12:24:26.370Z
Expanding on Colin's comment: Let X(A) be a statement about an oracle A. Let A' be any other oracle that differs with A on only finitely many inputs. If you can prove that whenever X(A) is true, X(A') is also true, then Pr(X(A)) is either 0 or 1. Most statements about Turing machines will be true if you modify the oracle at finitely many places, since you can hardcode finitely many values into a Turing machine's internal logic.
Robin Kothari
CC BY-SA 3.0
2012-09-18T15:50:44.543Z
@ColinMcQuillan: that should be an answer :).
Joshua Grochow
<cc.complexity-theory><relativization><random-oracles>
A natural result that relativized to a random oracle is true with probability 1/2
Kaveh
# A natural result that relativized to a random oracle is true with probability 1/2

(Asked by: username_0 on 2012-09-18)

There are several well known results regarding random oracles, e.g.

> $\mathsf{IP}^A \neq \mathsf{PSpace}^A$ for almost all oracles.

Are there any known natural examples where a similar statement is both true and false for significant fractions of the random oracles (e.g. it is true with probability $1/2$)?

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

> **Comments:**
> **username_1**: No interesting result will depend on the oracle's values on a particular finite set, so this seems to be ruled out by Kolmogorov's zero-one law.  
> **username_2**: Expanding on Colin's comment: Let X(A) be a statement about an oracle A. Let A' be any other oracle that differs with A on only finitely many inputs. If you can prove that whenever X(A) is true, X(A') is also true, then Pr(X(A)) is either 0 or 1. Most statements about Turing machines will be true if you modify the oracle at finitely many places, since you can hardcode finitely many values into a Turing machine's internal logic.  
> **username_3**: @ColinMcQuillan: that should be an answer :).  

---

## 0 answers

