A measure in which Boolean negation is exponentially powerful (Q790083)

In this paper relations between several complexity measures for families of Boolean functions, such as circuit size, formula size, and (monotone) representation size are presented. Roughly speaking, the circuit size of a Boolean function f is the smallest circuit and its formula size is the smallest Boolean function representing f. Furthermore, a family P of functions is a sequence \(\{P_ n\}_{n\in S}\) where \(P_ n\) is a function of n variables and \(S\subseteq N\). A family P is (monotone) universal if all (monotone) functions f are (monotone) projections of some members of P. The (monotone) representation size with respect to a (monotone) universal family P for a (monotone) function f is defined to be the smallest m such that f is a (monotone) projection of \(P_ m\).