On the Complexity of Negation-Limited Boolean Networks

DOI10.1137/S0097539794275136zbMATH Open0907.68079OpenAlexW2069191912MaRDI QIDQ4210099FDOQ4210099

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

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

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)

Cited In (22)

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

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)