Limiting negations in bounded-depth circuits: an extension of Markov's theorem

DOI10.1016/j.ipl.2004.01.003zbMath1177.68102OpenAlexW1974426418MaRDI QIDQ2390211

Shao Chin Sung, Keisuke Tanaka

Publication date: 21 July 2009

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.01.003

zbMATH Keywords

computational complexitycircuit complexitynegation-limited circuits

Mathematics Subject Classification ID

Related Items (1)

On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography

Cites Work

• Unnamed Item
• An exponential gap with the removal of one negation gate
• On the negation-limited circuit complexity of merging
• On the Inversion Complexity of a System of Functions
• Limiting Negations in Constant Depth Circuits
• On the Complexity of Negation-Limited Boolean Networks

This page was built for publication: Limiting negations in bounded-depth circuits: an extension of Markov's theorem