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

DOI10.1016/J.IPL.2004.01.003zbMATH Open1177.68102OpenAlexW1974426418MaRDI QIDQ2390211FDOQ2390211

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

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
• 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)

zbMATH Keywords

computational complexitycircuit complexitynegation-limited circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Limiting Negations in Constant Depth Circuits
• On the Inversion Complexity of a System of Functions
• Title not available (Why is that?)
• On the Complexity of Negation-Limited Boolean Networks
• An exponential gap with the removal of one negation gate
• On the negation-limited circuit complexity of merging

Cited In (4)

• Limiting Negations in Constant Depth Circuits
• Title not available (Why is that?)
• Algorithms and Computation
• On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography

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)