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)

• Ehrenfeucht-Fraïssé Games on Random Structures
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• The invariant problem for binary string structures and the parallel complexity theory of queries
• A logic for constant-depth circuits
• Symmetric circuits for rank logic
• Aggregate operators in constraint query languages
• A polynomial excluded-minor approximation of treedepth
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• On symmetric circuits and fixed-point logics
• Subspace-invariant \(\mathrm{AC}^0\) formulas
• Threshold circuits of small majority-depth
• On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
• Linear-size constant-depth polylog-threshold circuits
• Generalized lower bounds derived from Hastad's main lemma
• Properties of symmetric Boolean functions
• A logical characterization of constant-depth circuits over the reals
• Fixed-Point Definability and Polynomial Time

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)