Relating polynomial time to constant depth

DOI10.1016/S0304-3975(98)00061-9MaRDI QIDQ1274992zbMATH OpenFDO

Authors Heribert Vollmer

Publication date 12 January 1999

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(98)00061-9

zbMATH Keywords

Boolean circuitsconstant depth circuitsoracle separationspolynomial time classesTuring machines

Mathematics Subject Classification ID

Recommendations

• scientific article; zbMATH DE number 4125012
• Generic separations and leaf languages
• Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
• Relativized circuit complexity

Cites work

• A uniform approach to define complexity classes
• An oracle separating \(\oplus P\) from \(PP^{PH}\)
• Bounded Query Classes
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Depth reduction for circuits of unbounded fan-in
• Gap-languages and log-time complexity classes
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3917710 (Why is no real title available?)
• scientific article; zbMATH DE number 512860 (Why is no real title available?)
• scientific article; zbMATH DE number 1072527 (Why is no real title available?)
• scientific article; zbMATH DE number 1072530 (Why is no real title available?)
• scientific article; zbMATH DE number 1072537 (Why is no real title available?)
• scientific article; zbMATH DE number 1142303 (Why is no real title available?)
• scientific article; zbMATH DE number 1414291 (Why is no real title available?)
• scientific article; zbMATH DE number 1453080 (Why is no real title available?)
• Logspace and logtime leaf languages
• On the construction of parallel computers from various basis of Boolean functions
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Perceptrons, PP, and the polynomial hierarchy
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• PP is as Hard as the Polynomial-Time Hierarchy
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• The polynomial-time hierarchy
• The power of the middle bit of a \(\#\)P function

Cited in

(7)

• The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
• A characterization of definability of second-order generalized quantifiers with applications to non-definability
• Parity, circuits, and the polynomial-time hierarchy
• Constant Depth Reducibility
• Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy
• scientific article; zbMATH DE number 4125012 (Why is no real title available?)
• Generic separations and leaf languages

This page was built for publication: Relating polynomial time to constant depth

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