The Zero-One Law for Random Oracles

A couple of years ago, Rossman, Servedio and Tan showed that the polynomial-time hierarchy is infinite relative to a random oracle. That is if you choose each string independently to be in or out of an oracle R with probability one, the polynomial-time hierarchy will be infinite relative to R with probability one. This is one in the measure theory sense, there are oracles where it is false, it is just that those oracles will occur with zero probability.

There are still a few open questions for random oracles, such as whether P = BQP, quantum and classical computing can solve the same problems efficiently.. We suspect that P is different than BQP relative to a random oracle because otherwise BQP would be the same as BPP unrelativized (and thus factoring is easy), but we have no proof. Could it be possible that this problem has no simple resolution, that P = BQP holds with probability 1/2 relative to a random oracle, or some other probability strictly between 0 and 1? As it turns out no.

Some statements do hold with intermediate probabilities. The sentence "0101 in R" holds with probability 1/2. Even for a fixed machine M, questions like "M^R accepts an infinite language" could hold with probability say 3/8.

But statements like P = BQP relative to R can't happen with intermediate probability. That's due to the Kolmogorov zero-one law. If you have a subset of oracles that are closed under finite differences, that set must occur with probability zero or one. Every statement about complexity classes has that property because we can hard wire finite differences of the oracle into the machine description without increasing the running time. It will change the machine but not the complexity class. So P = BQP holds with probability zero or one even though we can't tell which one yet.

The Kolmogorov zero-one law gives us a consistent look at complexity classes. Since the countable union of zero probability events still has probability zero, every finitely-described statement about complexity classes that hold with probability one, all simultaneously hold with probability one. While this random world does not match the unrelativized one, it does give us a relativized world where we can explore the different possible relationships between complexity classes.