Computational complexity of Boolean functions

DOI10.1070/RM2012v067n01ABEH004777zbMath1257.94041OpenAlexW1993668330MaRDI QIDQ2892023

Aleksej Dmitrievich 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

lower boundsurvey paperBoolean functiondisjunctive normal formpartial Boolean functioncontact networkBoolean circuitcomplexity of circuitscellular circuitlogical formulaseries-parallel contact network

Mathematics Subject Classification ID

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

Related Items (4)

Totally optimal decision trees for Boolean functions ⋮ On implementation of Boolean functions by contact circuits of minimal uniform width ⋮ On implementation of Boolean functions by contact circuits with a constant uniform width ⋮ Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms

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