Relating polynomial time to constant depth

DOI10.1016/S0304-3975(98)00061-9zbMath0916.68038MaRDI QIDQ1274992

Heribert Vollmer

Publication date: 12 January 1999

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

zbMATH Keywords

Turing machinesBoolean circuitsconstant depth circuitsoracle separationspolynomial time classes

Mathematics Subject Classification ID

Related Items

A characterization of definability of second-order generalized quantifiers with applications to non-definability, The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis

Cites Work

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