Limiting negations in non-deterministic circuits
From MaRDI portal
Publication:837192
DOI10.1016/j.tcs.2009.05.018zbMath1170.94347OpenAlexW2077017336MaRDI QIDQ837192
Publication date: 10 September 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.018
Related Items (2)
On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography ⋮ Lower bounds for Boolean circuits of bounded negation width
Cites Work
- On the minimum number of negations leading to super-polynomial savings
- The monotone circuit complexity of Boolean functions
- 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
- Negation-Limited Inverters of Linear Size
- Limiting Negations in Constant Depth Circuits
- On the Complexity of Negation-Limited Boolean Networks
- Algorithms and Computation
- Characterizing non-deterministic circuit size
- A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Limiting negations in non-deterministic circuits
