Estimates for the complexity of a method for solving the problem of inclusive search

We suggest a method to solve the problem of inclusive search, which has three versions depending on the chosen base set: the set of monotone Boolean function, the set of elementary monotone conjunctions, and the set of Boolean variables. For each version, we estimate the Shannon function for the method complexity and the mean value of the complexity; we study the asymptotic behaviour of the Shannon function and of the logarithm of the mean value, and find that the Shannon function for the complexity of the method suggested asymptotically behaves as the Shannon function for the complexity of inclusive search.
This research was supported by the Russian Foundation for Basic Research, grant 98–01–00130.