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

Дискрет. матем., 1993, том 5, выпуск 3, страницы 64–75 (Mi dm691)

Пороговая функция в эффекте Шеннона для булевых функций относительно симметрической группы

О. В. Денисов


Аннотация: Доказывается, что если $A$ – свойство булевой функции $(x_1,\dots,x_n)$ веса $r$, заключающееся в том, что $f$ имеет тривиальную группу инерции относительно группы $S_n$, то функция $A(n)=\ln n$ является пороговой для свойства $A$.

УДК: 519.1

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


 Англоязычная версия: Discrete Mathematics and Applications, 1993, 3:5, 505–515

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


© МИАН, 2024