ECCC-Report TR97-057https://eccc.weizmann.ac.il/report/1997/057Comments and Revisions published for TR97-057en-usTue, 02 Dec 1997 15:57:56 +0200
Paper TR97-057
| Complexity and Probability of some Boolean Formulas |
Petr Savicky
https://eccc.weizmann.ac.il/report/1997/057 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.
Tue, 02 Dec 1997 15:57:56 +0200https://eccc.weizmann.ac.il/report/1997/057