A measure of relativized space which is faithful with respect to depth

DOI10.1016/0022-0000(88)90031-1zbMath0663.68061OpenAlexW2072573877MaRDI QIDQ1115190

Christopher B. Wilson

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(88)90031-1

zbMATH Keywords

NC hierarchyoracle stackrelativizing space classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (5)

Towards Computational Complexity Theory on Advanced Function Spaces in Analysis ⋮ Space-efficient informational redundancy ⋮ A survey of space complexity ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace ⋮ Relativizing small complexity classes and their theories

Cites Work

• Unnamed Item
• Unnamed Item
• Space-bounded hierarchies and probabilistic computations
• Relativized circuit complexity
• On uniform circuit complexity
• Relationships between nondeterministic and deterministic tape complexities
• A taxonomy of problems with fast parallel algorithms
• RelativizedNC
• On relativizing auxiliary pushdown machines
• Limitations on Separating Nondeterministic Complexity Classes
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Relativization of questions about log space computability
• On Relating Time and Space to Size and Depth

This page was built for publication: A measure of relativized space which is faithful with respect to depth