Realization of Boolean functions by formulas in continuous bases containing a continuum of constants

What is it about?

For an arbitrary Boolean function of n variables, we show how to construct formulas of complexity O(2^{n/2}) in the bases {x−y,xy,|x|}⋃[0,1],{x−y,x∗y,2x,|x|}⋃[0,1], {x−y,xy,|x|}⋃[0,1],{x−y,x∗y,2x,|x|}⋃[0,1], , where x * y = max(−1, min(1, x))max(−1, min(1, y)). The obtained estimates are, in general, order-sharp.

Featured Image