Том 4, серия 1, номер 3, 1997 г., Стр. 49-68

УДК 519.7
А. В. Чашкин
О вычислении булевых функций вероятностными программами

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

Чашкин А. В. ¹
1. МГУ, мех.-мат. факультет
Воробьевы горы, 119899 Москва, Россия

Статья поступила 7 апреля 1997 г.