On the Complexity of Negation-Limited Boolean Networks

DOI10.1137/S0097539794275136zbMath0907.68079OpenAlexW2069191912MaRDI QIDQ4210099

Tetsuro Nishino, Robert Beals, Keisuke Tanaka

Publication date: 20 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794275136

zbMATH Keywords

upper boundslower boundscircuit complexitynegation-limited circuit

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (10)

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 ⋮ Reductions for monotone Boolean circuits ⋮ Negation-limited formulas ⋮ Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences ⋮ Negation-limited complexity of parity and inverters ⋮ On Negations in Boolean Networks ⋮ On the minimum number of negations leading to super-polynomial savings ⋮ On the negation-limited circuit complexity of merging

This page was built for publication: On the Complexity of Negation-Limited Boolean Networks