On the minimum number of negations leading to super-polynomial savings
From MaRDI portal
Publication:1029051
DOI10.1016/j.ipl.2003.10.003zbMath1178.68283OpenAlexW1972349717MaRDI QIDQ1029051
Publication date: 9 July 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2003.10.003
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (3)
Limiting negations in non-deterministic circuits ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ On the mystery of negations in circuits: structure vs power
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monotone real circuits are more powerful than monotone Boolean circuits
- Lower bounds on monotone complexity of the logical permanent
- 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
- Monotone versus positive
- Limiting Negations in Constant Depth Circuits
- On the Complexity of Negation-Limited Boolean Networks
- Negation is Powerless for Boolean Slice Functions
- Combinatorics of monotone computations
This page was built for publication: On the minimum number of negations leading to super-polynomial savings