Circuit size relative to pseudorandom oracles
Jack H. Lutz, William J. Schmidt · 2002
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 in 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).>