Expressing uniformity via oracles

DOI10.1007/BF02679465zbMATH Open0872.68047OpenAlexW1971150371MaRDI QIDQ1361886FDOQ1361886

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

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

zbMATH Keywords

DLOGTIME

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Machines, Computations, and Universality
• 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)