Limiting Negations in Constant Depth Circuits
From MaRDI portal
Publication:4032939
DOI10.1137/0222022zbMath0770.68057OpenAlexW2038272454MaRDI QIDQ4032939
No author found.
Publication date: 17 May 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222022
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
The average sensitivity of bounded-depth circuits ⋮ Limiting negations in non-deterministic circuits ⋮ On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography ⋮ Limiting negations in bounded-depth circuits: an extension of Markov's theorem ⋮ Negation-limited circuit complexity of symmetric functions ⋮ On the mystery of negations in circuits: structure vs power ⋮ New bounds for energy complexity of Boolean functions ⋮ On the minimum number of negations leading to super-polynomial savings
