On monotone simulations on nonmonotone networks
From MaRDI portal
Publication:1121853
DOI10.1016/0304-3975(89)90142-4zbMath0674.94024OpenAlexW1963559764WikidataQ127152337 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 complexityslice functionsn-argument monotone Boolean functionsuperlinear lower boundssuperpolynomial complexity
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (2)
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
This page was built for publication: On monotone simulations on nonmonotone networks
