Relativized NC

From MaRDI portal





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 relativized NC and compare it under various oracles with relativized L, NL, and P. We see that \(NC_ 1\) is properly contaied in L if and only if there exists an oracle A such that \(NC_ 1^ A\) is properly contained in \(L^ A\). There is an oracle A where the hierarchy collapses, \(NC_ 1^ A=NC^ A\), and another where \(NC_ 1^ A\subset NC^ A_ 2\subset...\subset NC^ A\subset P^ A\). We then construct an A so that, for any k, \(NC^ A_ 1\) contains a set not in \(NSPACE^ A(O(n^ k))\), suggesting that the notion of relativized space is too weak or that of relativized depth is too strong.











This page was built for publication: Relativized NC

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3763591)