Negation is Powerless for Boolean Slice Functions
From MaRDI portal
Publication:4726175
DOI10.1137/0215037zbMath0616.94020OpenAlexW2043629999MaRDI QIDQ4726175
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215037
upper boundsBoolean functioncircuit complexitymonotone circuitslice functioncomplexity of minimal size Boolean circuits
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (11)
More on the complexity of slice functions ⋮ The complexity of central slice functions ⋮ Fast Möbius inversion in semimodular lattices and ER-labelable posets ⋮ \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice ⋮ On monotone simulations on nonmonotone networks ⋮ On \(\epsilon\)-sensitive monotone computations ⋮ On derandomization and average-case complexity of monotone functions ⋮ Fast monotone summation over disjoint sets ⋮ On Negations in Boolean Networks ⋮ On the minimum number of negations leading to super-polynomial savings ⋮ On the complexity of slice functions
This page was built for publication: Negation is Powerless for Boolean Slice Functions
