Circuit depth relative to a random oracle (Q1198081)

The study of separation of complexity classes with respect to random oracles was initiated by \textit{H. C. Bennett} and \textit{J. Gill} [SIAM J. Comput. 10, 96-113 (1981; Zbl 0454.68030)] and continued by many researchers. Computation relative to an oracle \(A\), where \(A\subseteq \{0,1\}^*\) is a computation which is allowed to ask queries of the form \(y\in A\)? and get answers. A random oracle \(A\) is simply a random (with respect to Lebesgue measure) subset of \(\{0,1\}^*\), i.e. for each \(x\in \{0,1\}^*\), \(x\in A\) with probability \(1/2\) and all these events are mutually independent. \textit{C. B. Wilson} [Math. Syst. Theory 20, 13-29 (1987; Zbl 0627.68043); SIAM J. Comput. 19, No. 2, 384-396 (1990; Zbl 0692.68045)] defined relativized circuit depth and constructed various oracles \(A\) for which \(P^ A\neq NC^ A\), \(NC^ A_ k\neq NC^ A_{k+\epsilon}\), \(AC^ A_ k\neq AC^ A_{k+\epsilon}\), \(AC^ A_ k\not\subseteq NC^ A_{k+1-\epsilon}\) and \(NC^ A_ k\not\subseteq AC^ A_{k-\epsilon}\) for all positive rational \(k\) and \(\epsilon\), thus separating those classes for which no trivial argument shows inclusion (the definition of \(NC^ A_ k\) and \(AC^ A_ k\) is restricted to rational \(k\) for constructibility reasons). 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 \(Q\) with probability 1.