zbMATH — the first resource for mathematics

Computational complexity of Boolean functions. (English. Russian original) Zbl 1257.94041
Russ. Math. Surv. 67, No. 1, 93-165 (2012); translation from Usp. Mat. Nauk 67, No. 1, 97-168 (2012).
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).
The reference list contains 165 titles.

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
06E30 Boolean functions
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI