Realizing Boolean Functions on Disjoint Sets of Variables

Abstract

For switching functions $f$ let $C(f)$ be the combinatorial complexity of $f$. We prove that for every $\varepsilon greater than 0$ there are arbitrarily complex functions $f:\{0,1\}^{n} \rightarrow \{0,1\}^{n}$ such that $C(fxf) \leq (1+ \varepsilon) C(f)$ and arbitrarily complex functions $g:\{0,1\}$ such that $C(v c(fxf)) \leq (1 + \varepsilon)C(f)$. These results and the techniques developed to obtain them are used to show, that Ashenhurst decomposition of switching functions does not always yield optimal circuits and to prove a new result concerning the trade-off between circuit size and monotone circuit size.