RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2015, том 27, выпуск 3, страницы 108–122 (Mi dm1338)

Среднее и дисперсия числа подфункций случайной булевой функции, близких к множеству аффинных функций

А. А. Серов

Математический институт им. В. А. Стеклова РАН

Аннотация: Для случайных равновероятных булевых функций изучается распределение количеств подфункций от заданного числа переменных, близких к множеству аффинных булевых функций. Показано, например, что для булевых функции от $n$ переменных математическое ожидание числа подфункций от $s\geqslant 3+\log_2 n$ переменных, расстояние Хэмминга от которых до множества аффинных функций меньше $2^{s-2}$, стремится к $0$ при $n\rightarrow\infty$.

Ключевые слова: случайная булева функция, подфункция, аффинные булевы функции, расстояние Хэмминга.

УДК: 519.212.2+519.213.2

Статья поступила: 17.02.2015

DOI: 10.4213/dm1338


 Англоязычная версия: Discrete Mathematics and Applications, 2017, 27:1, 23–34

Реферативные базы данных:


© МИАН, 2024