Negation is Powerless for Boolean Slice Functions

From MaRDI portal





This paper deals with upper bounds for the complexity of minimal size Boolean circuits. The question is, how much the complexity of a monotone circuit exceeds the complexity of the circuit over the universal basis \(\{\wedge,\vee,\neg \}\). If the kth slice function of a Boolean function \(f(x_ 1,...,x_ n)\) is defined to be equal to (i) \(f(x_ 1,...,x_ n)\) if exactly k inputs are 1, (ii) 0 if fewer than k inputs are one, and (iii) 1 if more than k inputs are one, then the function f is well represented by its \(n+1\) slices (they are of course monotone functions). The author shows that \[ C_{\wedge,\vee}(F)\leq 2C_{\wedge,\vee,\neg}(F)+O(n(\log n)^ 2), \] for all slice function sets F. This result differs in the additive term from the previously known \(O(n^ 2 \log n)\). The proof is based on the construction of monotone subcircuits that can merge two sorted lists of length m in O(m log m) gates.











This page was built for publication: Negation is Powerless for Boolean Slice Functions

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