Computational complexity of Boolean functions. (English. Russian original) Zbl 1257.94041

Korshunov, A. D.

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.

Reviewer: Ioan Tomescu (Bucureşti)

MSC:

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

Keywords:

survey paper; Boolean circuit; Boolean function; disjunctive normal form; cellular circuit; contact network; logical formula; lower bound; complexity of circuits; series-parallel contact network; partial Boolean function