Relativized NC
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.
- A 2.5n-Lower Bound on the Combinational Complexity of Boolean Functions
- A Boolean function requiring 3n network size
- A taxonomy of problems with fast parallel algorithms
- scientific article; zbMATH DE number 619538 (Why is no real title available?)
- Limitations on Separating Nondeterministic Complexity Classes
- On Relating Time and Space to Size and Depth
- On uniform circuit complexity
- Qualitative relativizations of complexity classes
- Quantitative Relativizations of Complexity Classes
- Relationships between nondeterministic and deterministic tape complexities
- Relativization of questions about log space computability
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativized circuit complexity
- Space-bounded hierarchies and probabilistic computations
- The network complexity and the Turing machine complexity of finite functions
- The polynomial-time hierarchy
- Relativized circuit complexity
- A measure of relativized space which is faithful with respect to depth
- An NL hierarchy
- Circuit depth relative to a random oracle
- On parallel hierarchies and R_k^i
- Separating NC along the \(\delta\) axis
- Equivalence of NC\(^ k\) and AC\(^{k-1}\) closures of NP and other classes
- Positive relativizations for log space computability
- scientific article; zbMATH DE number 4045155 (Why is no real title available?)
- Adaptive logspace reducibility and parallel time
- Relativized logspace and generalized quantifiers over finite ordered structures
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
- Parallel computation and the NC hierarchy relativized
- Relationships among $PL$, $\#L$, and the determinant
- The complexity class θp2: Recent results and applications in AI and modal logic
- Characterizations of some complexity classes between \(\Theta_2^{\mathrm{P}}\) and \(\Delta_2^{\mathrm{P}}\)
- On NC-real complexity classes for additive circuits and their relations with NC
- On parallel hierarchies and R ki
- A note on the relation between polynomial time functionals and Constable's class \(\mathcal K\)
- On adaptive DLOGTIME and POLYLOGTIME reductions
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)