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)

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)