Negation-limited circuit complexity of symmetric functions

DOI10.1016/0020-0190(96)00115-9zbMath0875.68431OpenAlexW2018836753WikidataQ126781571 ScholiaQ126781571MaRDI QIDQ671626

Robert Beals, Keisuke Tanaka, Tetsuro Nishino

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00115-9

zbMATH Keywords

Computational complexityTheory of computation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Asymptotics of growth for non-monotone complexity of multi-valued logic function systems ⋮ ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS ⋮ The minimum number of negations in circuits for systems of multi-valued functions ⋮ Negation-limited formulas ⋮ Negation-limited complexity of parity and inverters ⋮ An exponential gap with the removal of one negation gate

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• The monotone circuit complexity of Boolean functions
• The gap between monotone and non-monotone circuit complexity is exponential
• On the complexity of negation-limited Boolean networks
• On the Inversion Complexity of a System of Functions
• Limiting Negations in Constant Depth Circuits
• Monotone circuits for matching require linear depth
• Minimal Negative Gate Networks

This page was built for publication: Negation-limited circuit complexity of symmetric functions