On the complexity of 2-output Boolean networks

DOI10.1016/0304-3975(81)90074-8zbMath0473.94021OpenAlexW1976287608MaRDI QIDQ1159183

S. H. Smith

Publication date: 1981

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(81)90074-8

zbMATH Keywords

Boolean functionscombinational networkscombinational complexitymonotone network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (7)

\(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice ⋮ Super-logarithmic depth lower bounds via the direct sum in communication complexity ⋮ The choice and agreement problems of a random function ⋮ On the time-space complexity of reachability queries for preprocessed graphs ⋮ The direct sum of universal relations ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Minimal polynomials for the conjunction of functions on disjoint variables can be very simple

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of monotone networks for Boolean matrix product
• On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements
• Practical decidability
• The network complexity and the Turing machine complexity of finite functions
• Realizing Boolean functions on disjoint sets of variables
• The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging
• The Power of Negative Thinking in Multiplying Boolean Matrices
• The complexity of monotone boolean functions
• Relations Among Complexity Measures

This page was built for publication: On the complexity of 2-output Boolean networks