Relating polynomial time to constant depth
From MaRDI portal
Publication:1274992
DOI10.1016/S0304-3975(98)00061-9zbMath0916.68038MaRDI QIDQ1274992
Publication date: 12 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
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