With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

摘要

We consider how much error a fixed depth Boolean circuit must make in computing the parity function. We show that with an exponential bound of the form exp(nλ) on the size of the circuits, they make a 50% error on all possible inputs, asymptotically and uniformly. As a consequence, we show that a random oracle set A separates PSPACE from the entire polynomial-time hierarchy with probability one.