RelativizedNC

DOI10.1007/BF01692056zbMath0627.68043OpenAlexW4238805097MaRDI QIDQ3763591

Christopher B. Wilson

Publication date: 1987

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01692056

zbMATH Keywords

oraclesrelativized complexity classesrelativized depth for circuit familiesrelativized NCuniform families of relativized circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (13)

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

This page was built for publication: RelativizedNC