Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR97-057 | 3rd November 1997 00:00

#### Complexity and Probability of some Boolean Formulas

TR97-057
Authors: Petr Savicky
Publication: 2nd December 1997 15:57
Keywords:

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.

ISSN 1433-8092 | Imprint