Limiting negations in non-deterministic circuits
From MaRDI portal
Publication:837192
DOI10.1016/J.TCS.2009.05.018zbMATH Open1170.94347OpenAlexW2077017336MaRDI QIDQ837192FDOQ837192
Authors: Hiroki Morizumi 
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
Recommendations
Cites Work
- Title not available (Why is that?)
- The monotone circuit complexity of Boolean functions
- Title not available (Why is that?)
- Limiting Negations in Constant Depth Circuits
- On the Inversion Complexity of a System of Functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Complexity of Negation-Limited Boolean Networks
- A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates
- On the minimum number of negations leading to super-polynomial savings
- An exponential gap with the removal of one negation gate
- On the negation-limited circuit complexity of merging
- Negation-Limited Inverters of Linear Size
- Algorithms and Computation
- Characterizing non-deterministic circuit size
Cited In (9)
- Limiting Negations in Constant Depth Circuits
- A curious new result in switching theory
- On negation complexity of injections, surjections and collision-resistance in cryptography
- Inhibited Effects in CP-Logic
- Limiting negations in bounded-depth circuits: an extension of Markov's theorem
- Lower bounds for Boolean circuits of bounded negation width
- Negation-Limited Inverters of Linear Size
- Exact value of the nonmonotone complexity of Boolean functions
- Limiting Negations in Formulas
This page was built for publication: Limiting negations in non-deterministic circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q837192)
