The complexity of central slice functions

DOI10.1016/0304-3975(86)90122-2MaRDI QIDQ1084375zbMATH OpenOpenAlexFDO

Authors Paul E. Dunne

Publication date 1986

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

Full work available at URL https://doi.org/10.1016/0304-3975(86)90122-2

zbMATH Keywords

NP-completenessmonotone circuit complexitycombinational complexityk-slice of a Boolean function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• More on the complexity of slice functions
• scientific article; zbMATH DE number 3889430
• Negation is Powerless for Boolean Slice Functions
• On the complexity of slice functions
• On monotone simulations on nonmonotone networks

Cites work

• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• A Boolean function requiring 3n network size
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• Lower bounds on monotone complexity of the logical permanent
• More on the complexity of slice functions
• Negation is Powerless for Boolean Slice Functions
• On monotone simulations on nonmonotone networks
• On the complexity of slice functions

Cited in

(8)

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

This page was built for publication: The complexity of central slice functions

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