Abstract:
Given a binomial probability distribution on the $n$-dimensional Boolean cube, the complexity of implementation of Boolean functions by straight line programs with conditional stop is considered. The order, as $n\to\infty$, of the average-case complexity of almost all $n$-place Boolean functions is established.