The complexity of central slice functions

DOI10.1016/0304-3975(86)90122-2zbMath0605.94010OpenAlexW2051306408MaRDI QIDQ1084375

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) Complexity of computation (including implicit computational complexity) (03D15) Boolean functions (06E30)

Related Items (2)

\(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice ⋮ On monotone simulations on nonmonotone networks

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
• On monotone simulations on nonmonotone networks
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• Negation is Powerless for Boolean Slice Functions

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