A simplified proof of a lower complexity estimate

DOI10.1515/DMA-2013-010MaRDI QIDQ5396905zbMATH OpenOpenAlexFDO

Authors V. M. Khrapchenko

Publication date 4 February 2014

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma-2013-010

zbMATH Keywords

lower complexity bound

Mathematics Subject Classification ID

Boolean functions (06E30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Fuzzy sets and logic (in connection with information, communication, or circuits theory) (94D05)

Recommendations

• Circuit complexity and multiplicative complexity of Boolean functions
• scientific article; zbMATH DE number 4208009
• scientific article; zbMATH DE number 4031582
• Lower bounds on the formula complexity of a linear Boolean function
• scientific article; zbMATH DE number 609985

Cited in

(5)

• scientific article; zbMATH DE number 4031582 (Why is no real title available?)
• On the perfectness of minimal regular partitions of the edge set of the n-dimensional cube
• On the meaning of works by V. M. Khrapchenko
• Representations of normalized formulas
• On the structure of one class of perfect \(\Pi \)-partitions

This page was built for publication: A simplified proof of a lower complexity estimate

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