Circuit Depth Relative to a Random Oracle
Peter Bro Miltersen · DAIMI Report Series · 1991
The study of separation of complexity classes with respect to random oracles was initiated by Bennett and Gill and continued by many other authors. Wilson defined relativized circuit depth and constructed various oracles A for which P^A ¬ NC^A NC^A_k ¬ NC^A_k+varepsilon, AC^A_k ¬ AC^A_k+varepsilon, AC^A_k ¬ subset= AC^A_k+1-varepsilon, and NC^A_k not subset= AC^A_ k-varepsilon, for all positive rational k and varepsilon, thus separating those classes for which no trivial argument shows inclusion. In this note we show that as a consequence of a single lemma, these separations (or improvements of them) hold with respect to a random oracle A.