Definability by constant-depth polynomial-size circuits
DOI10.1016/S0019-9958(86)80006-7zbMATH Open0629.94023OpenAlexW1984534637MaRDI QIDQ3767263FDOQ3767263
Authors: Larry Denenberg, S. Shelah, Yuri Gurevich 
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80006-7
Recommendations
- scientific article; zbMATH DE number 1086678
- scientific article; zbMATH DE number 988809
- Circuit complexity and the expressive power of generalized first-order formulas
- First-order definability on finite structures
- scientific article; zbMATH DE number 1954387
- Decidability and undecidability of theories with a predicate for the primes
- scientific article
- scientific article; zbMATH DE number 3928955
- Some computational aspects of circumscription
Analysis of algorithms and problem complexity (68Q25) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Properties of classes of models (03C52) Complexity of computation (including implicit computational complexity) (03D15) Interpolation, preservation, definability (03C40)
Cited In (20)
- Title not available (Why is that?)
- Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
- Threshold circuits of small majority-depth
- Generalized lower bounds derived from Hastad's main lemma
- A logic for constant-depth circuits
- A polynomial excluded-minor approximation of treedepth
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
- Aggregate operators in constraint query languages
- Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- On symmetric circuits and fixed-point logics
- A logical characterization of constant-depth circuits over the reals
- Ehrenfeucht-Fraïssé Games on Random Structures
- First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
- Properties of symmetric Boolean functions
- Linear-size constant-depth polylog-threshold circuits
- Fixed-Point Definability and Polynomial Time
- Title not available (Why is that?)
- The invariant problem for binary string structures and the parallel complexity theory of queries
This page was built for publication: Definability by constant-depth polynomial-size circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3767263)
