Circuit size relative to pseudorandom oracles

Deterministic and nondeterministic circuit-size complexities are compared to deterministic and nondeterministic time complexities in the presence of pseudorandom oracles. Certain separations are shown to hold relative to every pspace-random oracle A, and relative to almost every oracle A∈ESPACE. In fact, these separations are shown to hold for almost every n. Since a randomly selected oracle is pspace-random with probability one, the separations immediately imply the corresponding random oracle separations, thus improving results of C.H. Bennett (1981) and J. Gill (1975) and answering open questions of C.B. Wilson (1985)