4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 8
    $\begingroup$ 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. $\endgroup$ – Colin McQuillan Sep 18 '12 at 9:12
  • 3
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Sep 18 '12 at 12:24
  • 1
    $\begingroup$ @ColinMcQuillan: that should be an answer :). $\endgroup$ – Joshua Grochow Sep 18 '12 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.