О вычислении булевых функций вероятностными программами

Изучается среднее время вычисления значений булевых функций неветвящимися программами, содержащими датчики случайных чисел. Рассматриваются как надежные программы, всегда вычисляющие истинное значение реализуемой функции, так и программы, вычисляющие искомые значения лишь с некоторой вероятностью. Показано, что в обоих случаях использование датчиков случайных чисел не приводит к заметному уменьшению среднего времени вычисления на значительной доле аргументов. Точнее, для любой булевой функции от $n$ аргументов, имеющей схемную сложность $L$, найдется область, на которой отношение $L$ к среднему времени вычисления надежными программами не превосходит $n$; при вычислении программами с вероятностью, отличной от единицы, это отношение может лишь незначительно превосходить $n$.
Библиогр. 10