On monotone simulations on nonmonotone networks
From MaRDI portal
Publication:1121853
DOI10.1016/0304-3975(89)90142-4zbMath0674.94024WikidataQ127152337 ScholiaQ127152337MaRDI QIDQ1121853
Publication date: 1989
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(89)90142-4
combinatorial complexity; slice functions; n-argument monotone Boolean function; superlinear lower bounds; superpolynomial complexity
Related Items
The complexity of central slice functions, \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
Cites Work
- Unnamed Item
- Unnamed Item
- A Boolean function requiring 3n network size
- On the complexity of slice functions
- Lower bounds on monotone complexity of the logical permanent
- More on the complexity of slice functions
- The complexity of central slice functions
- The monotone circuit complexity of Boolean functions
- Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
- A complexity theory based on Boolean algebra
- An Algorithm for the Computation of Linear Forms
- Negation is Powerless for Boolean Slice Functions