Realizing Boolean Functions on Disjoint Sets of Variables
Permanent Link(s)
Collections
Author
Paul, Wolfgang J.
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.
Date Issued
1975-10
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-215
Type
technical report