Том 7, серия 1, номер 3, 2000 г., Стр. 86-98
УДК 519.176
Д. Ю. Черухин
Нижние оценки формульной сложности симметрических булевых функций
Аннотация:
Для почти всех симметрических булевых функций от$n$ переменных, в частности для функции голосования, получены нижние оценки сложности вида$\Omega(n\log n)$ при реализации их формулами в произвольном конечном базисе.
Библиогр. 7.
Черухин Д. Ю. 1
1. МГУ, мех.-мат. факультет,
Воробьевы горы, 119899 Москва, Россия
е-mail: dyucher@mech.math.msu.su
Статья поступила 23 июня 2000 г.
