Том 6, серия 1, номер 3, 1999 г., Стр. 3-9
УДК 519.714
Ю. В. Мерекин
Нижние оценки мультипликативной сложности символьных последовательностей, определяемых монотонными симметрическими булевыми функциями
Аннотация:
Для мультипликативной сложности символьных последовательностей длины$2^n$ , являющихся столбцами значений монотонных симметрических булевых функций от$n$ переменных, в классе схем конкатенации слов получена нижняя оценка вида$n^2$ , асимптотически совпадающая с известной верхней оценкой. Аналогичный результат справедлив и для символьных последовательностей, определяемых элементарными симметрическими булевыми функциями.
Библиогр. 6.
Мерекин Ю. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: merekin@math.nsc.ru
Статья поступила 10 марта 1999 г.
