On the Complexity of Negation-Limited Boolean Networks

DOI10.1137/S0097539794275136MaRDI QIDQ4210099zbMATH OpenOpenAlexFDO

Authors Robert Beals, Tetsuro Nishino, 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

lower boundscircuit complexityupper boundsnegation-limited circuit

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of negation-limited Boolean networks (preliminary version)
• scientific article; zbMATH DE number 1263235
• Publication:4503971
• scientific article; zbMATH DE number 1379306
• Negation-limited complexity of parity and inverters

Cited in

(22)

• Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences
• A curious new result in switching theory
• Complexity of limit-cycle problems in Boolean networks
• On negation complexity of injections, surjections and collision-resistance in cryptography
• On the minimum number of negations leading to super-polynomial savings
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• On Negations in Boolean Networks
• scientific article; zbMATH DE number 1507247 (Why is no real title available?)
• Algorithms and Computation
• Negation-limited complexity of parity and inverters
• On the complexity of negation-limited Boolean networks (preliminary version)
• Negation-limited formulas
• SIMPLIFYING BOOLEAN NETWORKS
• On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
• On the negation-limited circuit complexity of merging
• Limiting Negations in Formulas
• scientific article; zbMATH DE number 176507 (Why is no real title available?)
• Reductions for monotone Boolean circuits
• Limiting negations in bounded-depth circuits: an extension of Markov's theorem
• Complexity of fixed point counting problems in Boolean networks
• Computing maximal and minimal trap spaces of Boolean networks
• Limiting negations in non-deterministic circuits

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210099)