Negation-limited circuit complexity of symmetric functions
From MaRDI portal
Publication:671626
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
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
