ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS

DOI10.17223/20710410/30/2OpenAlexW2918225822MaRDI QIDQ5150707

Vadim V. Kochergin, Anna Vital'evna Mikhailovich

Publication date: 15 February 2021

Published in: PRIKLADNAYa DISKRETNAYa MATEMATIKA (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/pdm524

zbMATH Keywords

logic circuitscircuit complexityBoolean circuitsMarkov's theoreminversion complexitybases with zero weight elementsBoolean function complexity

Mathematics Subject Classification ID

Computer science (68-XX) Information and communication theory, circuits (94-XX)

Related Items

On the Complexity of Multivalued Logic Functions over Some Infinite Basis ⋮ Asymptotics of growth for non-monotone complexity of multi-valued logic function systems ⋮ The minimum number of negations in circuits for systems of multi-valued functions ⋮ Exact value of the nonmonotone complexity of Boolean functions ⋮ Circuit complexity of \(k\)-valued logic functions in one infinite basis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• Negation-limited circuit complexity of symmetric functions
• On the Inversion Complexity of a System of Functions
• Negation-Limited Inverters of Linear Size
• Limiting Negations in Formulas
• Algorithms and Computation
• The Power of Negations in Cryptography
• Lattice Theoretic Properties of Frontal Switching Functions