Expressing uniformity via oracles

DOI10.1007/BF02679465zbMath0872.68047OpenAlexW1971150371MaRDI QIDQ1361886

Carsten Damm, Markus Holzer, Peter Rossmanith

Publication date: 28 July 1997

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

DLOGTIME

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Data independence of read, write, and control structures in PRAM computations

Cites Work

• Unnamed Item
• Relativized circuit complexity
• Tree-size bounded alternation
• On uniform circuit complexity
• Comparing complexity classes
• A note on multihead automata and context-sensitive languages
• On uniformity within \(NC^ 1\)
• P-uniform circuit complexity
• A taxonomy of problems with fast parallel algorithms
• Log Depth Circuits for Division and Related Problems
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• Alternation
• Inclusion complete tally languages and the Hartmanis-Berman conjecture

This page was built for publication: Expressing uniformity via oracles