__
TR97-057 | 3rd November 1997 00:00
__

#### Complexity and Probability of some Boolean Formulas

**Abstract:**
For any Boolean function $f$ let $L(f)$ be its formula size

complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and

every $k\le n/2$, we describe a probabilistic distribution

on formulas in the basis $\{\land,\oplus,1\}$ in some given set of

$n$ variables and of the size at most $l(k)=4^k$. Let $p_{n,k}(f)$

be the probability that the formula chosen from the distribution

computes the function $f$. For every function $f$ with

$L(f)\le l(k)^\alpha$, where $\alpha=\log_4(3/2)$, we have

$p_{n,k}(f)>0$. Moreover, for every function $f$, if $p_{n,k}(f)>0$,

then

$$(4n)^{-l(k)} \le p_{n,k}(f) \le c^{-l(k)^{1/4}},$$

where $c>1$ is an absolute constant. Although the upper and lower

bounds are exponentially small in $l(k)$, they are quasipolynomially

related whenever $l(k)\ge \ln^{\Omega(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.