Том 8, серия 1, номер 1, 2001 г., Стр. 77-93

УДК 519.7
А. В. Чашкин
О рандомизированной сложности функций, аппроксимирующих функцию голосования

Аннотация:
Рассматривается сложность реализации частичных булевых функций, приближающих булеву функцию от $n$ переменных, являющуюся булевой функцией голосования (по большинству) $M(x_1,\dots,x_n)$. Функции вычисляются на машине с произвольным доступом к памяти, снабженной генератором случайных чисел. Показано, что использование генераторов случайных чисел позволяет вычислять функции, грубо приближающие $M(x_1,\dots,x_n)$, за константное время. При вычислении функций, достаточно близких к $M(x_1,\dots,x_n)$, использование генераторов случайных чисел не позволяет более чем в константное число раз уменьшить сложность вычислений.
Библиогр. 7.

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

Статья поступила 22 июня 2000 г.