Abstract:
We consider average-case complexity of computing monotone Boolean functions by straight-line programs with a conditional stop over the basis of all Boolean functions of at most two variables. For the set of all $n$-ary monotone Boolean functions new Shannon-type upper and lower bounds for the average-case complexity as $n\to\infty$ are established.