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

DOI10.1016/J.IPL.2004.01.003MaRDI QIDQ2390211zbMATH OpenOpenAlexFDO

Authors S-C. 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

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Algorithms and Computation
• Limiting Negations in Constant Depth Circuits
• Limiting negations in non-deterministic circuits
• Limiting negations in bounded treewidth and upward planar circuits
• scientific article; zbMATH DE number 1263235
• Lower bounds for Boolean circuits of bounded negation width
• scientific article; zbMATH DE number 176507
• On the Complexity of Negation-Limited Boolean Networks
• Lower Bounds for DeMorgan Circuits of Bounded Negation Width
• On the complexity of negation-limited Boolean networks (preliminary version)

Cites work

• scientific article; zbMATH DE number 3513337 (Why is no real title available?)
• An exponential gap with the removal of one negation gate
• Limiting Negations in Constant Depth Circuits
• On the Complexity of Negation-Limited Boolean Networks
• On the Inversion Complexity of a System of Functions
• On the negation-limited circuit complexity of merging

Cited in

(5)

• Limiting Negations in Constant Depth Circuits
• scientific article; zbMATH DE number 176507 (Why is no real title available?)
• Learning circuits with few negations
• On negation complexity of injections, surjections and collision-resistance in cryptography
• Algorithms and Computation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2390211)