We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Expressing Uniformity via Oracles.
- Authors
Damm, C.; Holzer, M.; Rossmanith, P.
- Abstract
We study under what circumstances different uniformity notions for Boolean circuits of logarithmic depth lead to the same complexity class. Our investigations are based on a characterization of uniformity in terms of oracle access to tally sets that is proved in the present paper: A-uniform circuits of logarithmic depth are of the same computational power as DLOGTIME-uniform circuits of logarithmic depth with oracle access to tally sets in A. This characterization does not only apply to classes A such as logarithmic space or polynomial time, but to all in some sense 'well-behaved' classes and especially to all standard complexity classes. We present many applications for this characterization, among them upward separations, depth-uniformity tradeoffs, and inclusion-completeness results for tally languages.
- Subjects
LOGARITHMIC functions; COMPUTATIONAL complexity
- Publication
Theory of Computing Systems, 1997, Vol 30, Issue 4, p355
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s002240000056