Аннотация:
Предложен новый прием реализации формулами оператора подсчета количества единиц в булевом наборе, основанный на приближенном вычислении суммы. С его помощью неконструктивно получены новые верхние оценки сложности и глубины формул для произвольных и некоторых конкретных симметрических функций над базисом B2 всех двухместных булевых функций и над стандартным базисом B0={∧,∨,¯¯¯a}. В частности, глубина умножения n-разрядных двоичных чисел оценивается сверху асимптотически как 4,02log2n над базисом B2 и как 5,14log2n над базисом B0.
Образец цитирования:
И. С. Сергеев, “О сложности и глубине формул для симметрических булевых функций”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2016, № 3, 53–57; Moscow University Mathematics Bulletin, 71:3 (2016), 127–130
\RBibitem{Ser16}
\by И.~С.~Сергеев
\paper О сложности и глубине формул для симметрических булевых функций
\jour Вестн. Моск. ун-та. Сер.~1. Матем., мех.
\yr 2016
\issue 3
\pages 53--57
\mathnet{http://mi.mathnet.ru/vmumm155}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3637827}
\transl
\jour Moscow University Mathematics Bulletin
\yr 2016
\vol 71
\issue 3
\pages 127--130
\crossref{https://doi.org/10.3103/S0027132216030098}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000393855600009}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84980335801}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm155
https://www.mathnet.ru/rus/vmumm/y2016/i3/p53
Эта публикация цитируется в следующих 4 статьяx:
И. С. Сергеев, “Формульная сложность линейной функции в k-арном базисе”, Матем. заметки, 109:3 (2021), 419–435; I. S. Sergeev, “Formula Complexity of a Linear Function in a k-ary Basis”, Math. Notes, 109:3 (2021), 445–458
С. Б. Гашков, И. С. Сергеев, “О значении работ В. М. Храпченко”, ПДМ, 2020, № 48, 109–124
С. Б. Гашков, И. С. Сергеев, “Умножение”, Чебышевский сб., 21:1 (2020), 101–134
И. С. Сергеев, “Верхние оценки сложности и глубины формул для MOD-функций”, Дискрет. матем., 28:2 (2016), 108–116; I. S. Sergeev, “Upper bounds for the size and the depth of formulae for MOD-functions”, Discrete Math. Appl., 27:1 (2017), 15–22
Цитирование в формате AMSBIB
Обратная связь: