RelativizedNC

This paper introduces a notion of relativized depth for circuit families and discusses issues regarding uniform families of relativized circuits. This allows us to define a version of relativizedNC and compare it under various oracles with relativizedL, NL, andP. We see thatNC ₁ is properly contained inL if and only if there exists an oracleA such thatNC ₁ ^A is properly contained inL ^A . There is an oracleA where the hierarchy collapses,NC ₁ ^A = NC ^A , and another whereNC ₁ ^A NC ₂ ^A NC ^A P ^A . We then construct anA so that, for anyk, NC ₁ ^A contains a set not inNSPACE ^A (O(n ^k )), suggesting that the notion of relativized space is too weak or that of relativized depth is too strong.