On the complexity and depth of circuits that realize partial Boolean functions

DOI10.1515/DMA.1997.7.2.113MaRDI QIDQ4367622zbMATH OpenOpenAlexFDO

Authors A. V. Chashkin

Publication date 28 January 1998

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

Full work available at URL https://doi.org/10.1515/dma.1997.7.2.113

zbMATH Keywords

complexitydepthcircuitspartial Boolean functions

Mathematics Subject Classification ID

Boolean functions (06E30)

Recommendations

• scientific article; zbMATH DE number 4187721
• On estimates on the complexity of restrictions of Boolean functions
• On the complexity of restrictions of Boolean functions
• On the complexity of realizing the powers of a Boolean \((n,n)\)-function
• scientific article; zbMATH DE number 6004901

Cited in

(15)

• On the dependence of the complexity and depth of reversible circuits consisting of NOT, CNOT, and 2-CNOT gates on the number of additional inputs
• Signatures of Knowledge for Boolean Circuits Under Standard Assumptions
• scientific article; zbMATH DE number 4204280 (Why is no real title available?)
• scientific article; zbMATH DE number 15477 (Why is no real title available?)
• scientific article; zbMATH DE number 4187721 (Why is no real title available?)
• scientific article; zbMATH DE number 6004901 (Why is no real title available?)
• Signatures of knowledge for Boolean circuits under standard assumptions
• Using Flexibility in P-Circuits by Boolean Relations
• The complexity of the descriptiveness of Boolean circuits over different sets of gates
• On the VC-dimension of depth four threshold circuits and the complexity of Boolean-valued functions
• scientific article; zbMATH DE number 3863114 (Why is no real title available?)
• On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
• Parity, circuits, and the polynomial-time hierarchy
• Universal Perceptron Theory on Decomposition Structures of n-Bit Boolean Functions
• On the minimal memory volume that is necessary for realization of boolean function by conveyor boolean circuits

This page was built for publication: On the complexity and depth of circuits that realize partial Boolean functions

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