Definability by constant-depth polynomial-size circuits

DOI10.1016/S0019-9958(86)80006-7zbMath0629.94023OpenAlexW1984534637MaRDI QIDQ3767263

Larry Denenberg, Saharon 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) Complexity of computation (including implicit computational complexity) (03D15) Properties of classes of models (03C52) Interpolation, preservation, definability (03C40) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Related Items

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