Definability by constant-depth polynomial-size circuits

DOI10.1016/S0019-9958(86)80006-7MaRDI QIDQ3767263zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

first-order definabilitycircuit definabilitymonadic predicate symbolssequences of Boolean circuits

Mathematics Subject Classification ID

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)

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; zbMATH DE number 5510997
• scientific article; zbMATH DE number 3928955
• Some computational aspects of circumscription

Cited in

(20)

• Threshold circuits of small majority-depth
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Generalized lower bounds derived from Hastad's main lemma
• A polynomial excluded-minor approximation of treedepth
• A logic for constant-depth circuits
• 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
• Symmetric circuits for rank logic
• Subspace-invariant \(\mathrm{AC}^0\) formulas
• 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
• 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)