On the complexity of negation-limited Boolean networks

DOI10.1145/195058.195099zbMath1345.68166OpenAlexW2044799855MaRDI QIDQ2817595

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

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

Related Items (4)

Asymptotics of growth for non-monotone complexity of multi-valued logic function systems ⋮ Negation-limited circuit complexity of symmetric functions ⋮ On the minimum number of negations leading to super-polynomial savings ⋮ Non-cancellative Boolean circuits: A generalization of monotone boolean circuits

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