RelativizedNC

DOI10.1007/BF01692056MaRDI QIDQ3763591zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Parallel computation and the NC hierarchy relativized
• Relativized circuit complexity
• A measure of relativized space which is faithful with respect to depth

Cites work

• 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

Cited in

(20)

• 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: RelativizedNC

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