Computational complexity of Boolean functions (Q2892023)

This survey is devoted to a brief presentation, without complete proofs, of the main results over the last sixty years related to the complexity of computation (realization) of Boolean functions by contact networks, Boolean circuits, and Boolean circuits without branching. It contains three parts: Contact networks (arbitrary contact networks, series-parallel networks, planar networks, locally non-planar networks, cellular networks, networks without zero chains, networks of bounded degree, Khrapchenko's method for \(\pi\)-networks, symmetric Boolean functions, invariant classes of Boolean functions, lower bounds for the complexity of minimal contact networks, disjunctive normal forms), Boolean circuits (arbitrary Boolean circuits, circuits with bounded branching, threshold circuits, circuits with delays, cellular circuits, circuits over infinite bases, circuits over bases containing elements with zero weights, Lupanov's principle of local coding, partial Boolean functions, depth and delays of Boolean circuits, implicit and parametric expressibility of Boolean functions, polynomial lower bounds and high lower bounds for the complexity of Boolean circuits, methods of Razborov and Andreev), Boolean circuits without branching (complexity, circuits over bases containing elements with zero weights, depth and complexity, lower bounds for the complexity of Boolean circuits that compute particular Boolean functions).NEWLINENEWLINE The reference list contains 165 titles.