
doi: 10.1007/bf01692056
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.
relativized depth for circuit families, Analysis of algorithms and problem complexity, uniform families of relativized circuits, relativized NC, relativized complexity classes, oracles
relativized depth for circuit families, Analysis of algorithms and problem complexity, uniform families of relativized circuits, relativized NC, relativized complexity classes, oracles
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 27 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
