О среднем времени вычисления значений булевых функций

Рассматривается задача о среднем времени вычисления булевых функций неветвящимися программами с условной остановкой, состоящими из операторов двух типов. Каждый оператор первого типа вычисляет значение некоторой двуместной булевой функции, аргументами которой могут быть либо величины, вычисленные предыдущими операторами, либо значения входных переменных. Каждый оператор второго типа либо прерывает работу программы, либо дает указание выполнять очередной оператор. Мерой сложности таких программ является среднее время работы относительно всех наборов значений входных переменных. Доказано, что сложность реализации почти всех всюду определенных и почти всех частично определенных булевых функций такими программами по порядку совпадает со сложностью обычных схем из функциональных элементов, а для почти всех $n$-местных булевых функций, принимающих значение 1 на $n^c$ наборах, эти сложности с точностью до порядка различаются в $n$ раз. Установлено существование булевых функций от $n$ переменных, среднее время вычисления которых по порядку в $(2^n/n)^{1/2}$ раз меньше времени, необходимого для вычисления обычными неветвящимися программами.
Библиогр. 3