The exact circuit complexity of Boolean functions in an infinite basis

DOI10.1134/S0001434625030241MaRDI QIDQ6970163zbMATH OpenFDO

Authors Vadim V. Kochergin, Anna Vital'evna Mikhailovich

Publication date 18 June 2025

Published in Mathematical Notes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S0001434625030241

zbMATH Keywords

circuit complexitycircuit of functional gatesinfinite basislogic (Boolean) circuitnegation (inversion) complexity

Mathematics Subject Classification ID

Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Cites work

• Asymptotics of growth for non-monotone complexity of multi-valued logic function systems
• Boolean function complexity. Advances and frontiers.
• Circuit complexity of symmetric Boolean functions in antichain basis
• Exact value of the nonmonotone complexity of Boolean functions
• scientific article; zbMATH DE number 3513337 (Why is no real title available?)
• scientific article; zbMATH DE number 3607492 (Why is no real title available?)
• scientific article; zbMATH DE number 194333 (Why is no real title available?)
• scientific article; zbMATH DE number 3273218 (Why is no real title available?)
• scientific article; zbMATH DE number 3319974 (Why is no real title available?)
• scientific article; zbMATH DE number 3348015 (Why is no real title available?)
• scientific article; zbMATH DE number 3405844 (Why is no real title available?)
• scientific article; zbMATH DE number 3419055 (Why is no real title available?)
• Improvement of nonmonotone complexity estimates of k-valued logic functions
• Lattice Theoretic Properties of Frontal Switching Functions
• On the complexity of multivalued logic functions over some infinite basis
• On the Inversion Complexity of a System of Functions
• The minimum number of negations in circuits for systems of multi-valued functions

This page was built for publication: The exact circuit complexity of Boolean functions in an infinite basis

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