Том 11, серия 1, номер 3, 2004 г., Стр. 3-15

УДК 519.7
Р. Н. Забалуев
О средней сложности булевых функций, заданных полиномами Жегалкина

Аннотация:
Рассматривается сложность реализации булевых функций, заданных полиномами Жегалкина степени не более $k$, неветвящимися программами с условной остановкой. Показано, что средняя сложность почти каждого полинома от $n$ переменных, степень которого не превосходит $k$, не меньше $\frac38\frac S{\log_2S}(1+o(1))$, где $S=\sum_{i=0}^k\binom ni$ и $n\to\infty$. Доказано, что для более половины значений $k$ средняя сложность каждого полинома от $n$ переменных степени $k$ не превосходит величины $(1/2)\frac S{\log_2 S}(1+o(1))$, $n\to\infty$.

Забалуев Р. Н. ¹
1. МГУ, Мех.–мат. факультет, Воробьевы горы,
119992 Москва, Россия

Статья поступила 15 апреля 2004 г.