В работе изучается среднее время вычисления значений частичных булевых функций заданного веса неветвящимися программами с условной остановкой. Предложен новый метод вычисления таких функций, заключающийся в аппроксимации вычисляемой функции последовательностью более простых частичных функций. Получены новые совпадающие по порядку верхние и нижние оценки соответствующей функции Шеннона. Из полученных оценок следует, что средняя сложность почти всех рассматриваемых функций с точность до постоянного множителя зависит от веса w вычисляемой функции, не зависит от размера ее области определения и равна θ(w/log₂w).

сложность, функция Шеннона, булева функция, частичная функция

Математические вопросы и теория численных методов