Circuit Depth Relative to a Random Oracle

Abstract

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.