On monotone simulations on nonmonotone networks

DOI10.1016/0304-3975(89)90142-4MaRDI QIDQ1121853zbMATH OpenOpenAlexWikidataFDO

Authors Paul E. Dunne

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

zbMATH Keywords

combinatorial complexityn-argument monotone Boolean functionslice functionssuperlinear lower boundssuperpolynomial complexity

Mathematics Subject Classification ID

Recommendations

• Negation is Powerless for Boolean Slice Functions
• On the complexity of slice functions
• The complexity of central slice functions
• More on the complexity of slice functions
• scientific article; zbMATH DE number 3867233

Cites work

• A Boolean function requiring 3n network size
• A complexity theory based on Boolean algebra
• An Algorithm for the Computation of Linear Forms
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• scientific article; zbMATH DE number 3889430 (Why is no real title available?)
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• Lower bounds on monotone complexity of the logical permanent
• More on the complexity of slice functions
• Negation is Powerless for Boolean Slice Functions
• On the complexity of slice functions
• The complexity of central slice functions
• The monotone circuit complexity of Boolean functions

Cited in

(6)

• More on the complexity of slice functions
• The complexity of central slice functions
• On the planar monotone computation of Boolean functions
• \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
• scientific article; zbMATH DE number 3889430 (Why is no real title available?)
• Negation is Powerless for Boolean Slice Functions

This page was built for publication: On monotone simulations on nonmonotone networks

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