УДК 519.714

О сложности и глубине формул для симметрических булевых функций / И. С. Сергеев. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2016. № 3. С. 53-57.

Предложен новый прием реализации формулами оператора подсчета количества единиц в булевом наборе, основанный на приближенном вычислении суммы. С его помощью неконструктивно получены новые верхние оценки сложности и глубины формул для произвольных и некоторых конкретных симметрических функций над базисом B_2 всех двухместных булевых функций и над стандартным базисом B_0 =\{ \wedge, \vee,\overline{\phantom a} \}. В частности, глубина умножения n-разрядных двоичных чисел оценивается сверху асимптотически как 4,02\log_2n над базисом B_2 и как 5,14\log_2n над базисом B_0.

Ключевые слова: булевы формулы, сложность формул, глубина, симметрические булевы функции, умножение.

Библиогр. 9.

К оглавлению номера  Go!