Parallel computation and the NC hierarchy relativized

DOI10.1007/3-540-16486-3_111zbMath0615.68039OpenAlexW1854307478MaRDI QIDQ4723303

Christopher B. Wilson

Publication date: 1986

Published in: Structure in Complexity Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-16486-3_111

zbMATH Keywords

parallel computationrelativizationoracle stackrelativized depth for circuit familiesrelativized NCuniform families of relativized circuitsrelativized spaceuniform bounded fan-in Boolean circuit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Relativized alternation and space-bounded computation ⋮ A new complete language for DSPACE(log n) ⋮ Logics capturing relativized complexity classes uniformly ⋮ Space bounded computations: Review and new separation results ⋮ Characterizing parallel hierarchies by reducibilities