On the complexity of negation-limited Boolean networks (preliminary version)

DOI10.1145/195058.195099MaRDI QIDQ2817595zbMATH OpenOpenAlexFDO

Authors Keisuke Tanaka, Tetsuro Nishino

Publication date 1 September 2016

Published in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/195058.195099

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the Complexity of Negation-Limited Boolean Networks
• scientific article; zbMATH DE number 1263235
• Negation-limited complexity of parity and inverters
• Publication:4503971
• scientific article; zbMATH DE number 1379306

Cited in

(19)

• Negation-limited complexity of parity and inverters
• On the minimum number of negations leading to super-polynomial savings
• Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
• Asymptotics of growth for non-monotone complexity of multi-valued logic function systems
• On the negation-limited circuit complexity of merging
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• Limiting negations in bounded-depth circuits: an extension of Markov's theorem
• Limiting negations in bounded treewidth and upward planar circuits
• Limiting Negations in Formulas
• On the Complexity of Negation-Limited Boolean Networks
• scientific article; zbMATH DE number 1405685 (Why is no real title available?)
• Negation-Limited Complexity of Parity and Inverters
• A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates
• A curious new result in switching theory
• On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
• Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
• Negation-limited circuit complexity of symmetric functions
• Negation-limited formulas
• Complexity of limit-cycle problems in Boolean networks

This page was built for publication: On the complexity of negation-limited Boolean networks (preliminary version)

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