On the implementation of monotone Boolean functions by memoryless programs

The average-case complexity of computing monotone Boolean functions by straight line programs without memory with a conditional stop in the basis of all Boolean functions of at most two variables is considered. For the set of all monotone Boolean functions of $n$ variables, Shannon-type upper and lower bounds for the average-case complexity are established for $n\to\infty$.