RelativizedNC
From MaRDI portal
Publication:3763591
DOI10.1007/BF01692056zbMath0627.68043OpenAlexW4238805097MaRDI QIDQ3763591
Publication date: 1987
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01692056
oraclesrelativized complexity classesrelativized depth for circuit familiesrelativized NCuniform families of relativized circuits
Related Items
The complexity class θp2: Recent results and applications in AI and modal logic, Positive relativizations for log space computability, A measure of relativized space which is faithful with respect to depth, On parallel hierarchies and \(R_k^i\), Characterizations of some complexity classes between Θ2p and Δ2p, On parallel hierarchies and R ki, Adaptive logspace reducibility and parallel time, Relationships among $PL$, $\#L$, and the determinant, Relativized logspace and generalized quantifiers over finite ordered structures, On adaptive DLOGTIME and POLYLOGTIME reductions, Circuit depth relative to a random oracle, Complexity classes between $\Theta _k^P$ and $\Delta _k^P$, Relativizing small complexity classes and their theories
Cites Work
- Unnamed Item
- A Boolean function requiring 3n network size
- Qualitative relativizations of complexity classes
- Space-bounded hierarchies and probabilistic computations
- Relativized circuit complexity
- On uniform circuit complexity
- The network complexity and the Turing machine complexity of finite functions
- The polynomial-time hierarchy
- Relationships between nondeterministic and deterministic tape complexities
- A taxonomy of problems with fast parallel algorithms
- Quantitative Relativizations of Complexity Classes
- Limitations on Separating Nondeterministic Complexity Classes
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativization of questions about log space computability
- A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
- On Relating Time and Space to Size and Depth
