For any Boolean function f let L(f) be its formula size complexity in the basis 1 . For every n and every kn2 , we describe a probabilistic distribution on formulas in the basis 1 in some given set of n variables and of the size at most l(k)=4k. Let pnk(f) be the probability that the formula chosen from the distribution computes the function f. For every function f with L(f)l(k), where =log4(32) , we have pnk(f)0. Moreover, for every function f, if pnk(f)0, then (4n)?l(k)pnk(f)c?l(k)14 where c1 is an absolute constant. Although the upper and lower bounds are exponentially small in l(k), they are quasipolynomially related whenever l(k)ln(1)n. The construction is a step towards developping a model appropriate for investigation of the properties of a typical (random) Boolean function of some given complexity.
展开▼
