Computational complexity of Boolean functions

DOI10.1070/RM2012V067N01ABEH004777MaRDI QIDQ2892023zbMATH OpenOpenAlexFDO

Authors A. D. Korshunov

Publication date 18 June 2012

Published in Russian Mathematical Surveys (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1070/rm2012v067n01abeh004777

zbMATH Keywords

Boolean circuitBoolean functioncellular circuitcomplexity of circuitscontact networkdisjunctive normal formlogical formulalower boundpartial Boolean functionseries-parallel contact networksurvey paper

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10)

Review text

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.

Cited in

(21)

• On estimates on the complexity of restrictions of Boolean functions
• On implementation of Boolean functions by contact circuits with a constant uniform width
• Complexity of sequential implementation of partial Boolean functions
• On implementation of Boolean functions by contact circuits of minimal uniform width
• scientific article; zbMATH DE number 4176981 (Why is no real title available?)
• Totally optimal decision trees for Boolean functions
• scientific article; zbMATH DE number 4170848 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 42045 (Why is no real title available?)
• scientific article; zbMATH DE number 139638 (Why is no real title available?)
• Algorithms for Boolean Function Query Properties
• Local complexity of Boolean functions
• scientific article; zbMATH DE number 194333 (Why is no real title available?)
• scientific article; zbMATH DE number 953683 (Why is no real title available?)
• Monotone Boolean functions
• Boolean complexity classes vs. their arithmetic analogs
• On the meaning of works by V. M. Khrapchenko
• Complexity of Linear Boolean Operators
• Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms
• The complexity of Boolean functions in different characteristics
• Topological aspects of Boolean functions

This page was built for publication: Computational complexity of Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2892023)