# A natural result that relativized to a random oracle is true with probability 1/2

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$)?

• 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 Sep 18 '12 at 9:12
• 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 Sep 18 '12 at 12:24
• @ColinMcQuillan: that should be an answer :). – Joshua Grochow Sep 18 '12 at 15:50