Оценки сложности одного метода решения задачи включающего поиска

В работе предлагается метод решения задачи включающего поиска, имеющий три модификации в зависимости от выбранного базового множества: множества монотонных булевых функций, множества элементарных монотонных конъюнкций и множества булевых переменных. Для каждой из модификаций оценивается функция Шеннона сложности метода и среднее значение сложности, причем для функций Шеннона сложности метода найдена асимптотика, совпадающая с асимптотикой функции Шеннона сложности включающего поиска, а для среднего значения — асимптотика логарифма.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, грант 98-01-00130.