Expressing uniformity via oracles

DOI10.1007/BF02679465MaRDI QIDQ1361886zbMATH OpenOpenAlexFDO

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

Recommendations

• Random oracles and non-uniformity
• Generic oracles, uniform machines, and codes
• scientific article; zbMATH DE number 2167522
• Publication:4733402
• Oracle separation in the non-uniform model
• Uniform Proof Complexity
• Generalized computations with oracles
• scientific article; zbMATH DE number 4079399
• scientific article; zbMATH DE number 1555186
• Uniformity, universality, and computability theory

Cites work

• scientific article; zbMATH DE number 45125 (Why is no real title available?)
• A note on multihead automata and context-sensitive languages
• A taxonomy of problems with fast parallel algorithms
• Alternation
• Comparing complexity classes
• Inclusion complete tally languages and the Hartmanis-Berman conjecture
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• Log Depth Circuits for Division and Related Problems
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• P-uniform circuit complexity
• Relativized circuit complexity
• Tree-size bounded alternation

Cited in

(6)

• AND and/or OR: uniform polynomial-size circuits
• Machines, Computations, and Universality
• The lower reaches of circuit uniformity
• Extensional Uniformity for Boolean Circuits
• Data independence of read, write, and control structures in PRAM computations
• Generic oracles, uniform machines, and codes

This page was built for publication: Expressing uniformity via oracles

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