An exponential gap with the removal of one negation gate

DOI10.1016/S0020-0190(01)00264-2zbMath1015.68519OpenAlexW2053969720MaRDI QIDQ1603543

Keisuke Tanaka, Shao Chin Sung

Publication date: 14 July 2002

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00264-2

zbMATH Keywords

computational complexitycircuit complexitynegation-limited circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Limiting negations in non-deterministic circuits, Limiting negations in bounded-depth circuits: an extension of Markov's theorem, Reductions for monotone Boolean circuits

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Negation-limited circuit complexity of symmetric functions
• The monotone circuit complexity of Boolean functions
• The gap between monotone and non-monotone circuit complexity is exponential
• On the Inversion Complexity of a System of Functions
• On the Shannon capacity of a graph
• Monotone circuits for matching require linear depth