Bounds for the average-case complexity of monotone Boolean functions
Александр Викторович Чашкин · Discrete Mathematics and Applications · 2017
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 → ∞ are established.