УДК 519.714
О сложности и глубине формул для симметрических булевых функций / И. С. Сергеев. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2016. № 3. С. 53-57.
Предложен новый прием реализации формулами оператора
подсчета количества единиц в булевом наборе, основанный на
приближенном вычислении суммы. С его помощью неконструктивно
получены новые верхние оценки сложности и глубины формул для
произвольных и некоторых конкретных симметрических функций над
базисом
Ключевые слова: булевы формулы, сложность формул, глубина, симметрические булевы функции, умножение.
Библиогр. 9.