Полиномиальные представления булевых функций активно исследуются в связи с применением в теории кодирования и для синтеза схем цифровых устройств, начиная с основопологающей работы Мюллера. Операторный подход к полиномиальным представлениям предложенный в работах Винокурова позволил, с одной стороны, единообразно описать все известные виды полиномиальных форм булевых функций, с другой стороны, обобщить их на случай разложений по образом нечетных функций, отличных от конъюнкции.

При исследовании полиномиальных и, в общем случае, операторных форм один из главных вопросов - это получение оценок сложности представления булевых функций в различных классах форм. Верхние оценки сложности фактически представляют собой алгоритмы минимизации булевых функций в том или ином классе форм.

Нижние оценки сложности можно разделить на два вида: комбинаторные и эффективные. Комбинаторные оценки позволяют доказать существование булевых функций, имеющих высокую сложность, без нахождения явного вида этих функций. Эффективные же нижние оценки основаны на конструировании в явном виде булевых функций, имеющих высокую сложность в том или ином классе форм.

В настоящей работе с использованием алгебраического расширения конечного поля порядка 2 получена нижняя оценка сложности булевых функций в классе расширенных операторных форм. Данная оценка усиливает ранее известные оценки для данного класса операторных форм и будет являться асимптотически оптимальной в случае, если последовательность простых чисел Мерсенна бесконечна.

Балюк Александр Сергеевич, канд. физ.-мат. наук, доц., Иркутский государственный университет, Российская Федерация, 664003, Иркутск, ул. К. Маркса, 1, тел.: (3952)242210, e-mail: sacha@hotmail.ru

Baliuk A.S. Complexity Lower Bound for Boolean Functions in the Class of Extended Operator Forms // Известия Иркутского государственного университета. Серия Математика. 2019. Т. 30. С.125-140. https://doi.org/10.26516/1997-7670.2019.30.125

1. A000043 - OEIS // The On-Line Encyclopedia of Integer Sequences. URL: https://oeis.org/A000043 (дата обращения: 24.08.2019)
2. Балюк А. С., Зинченко А. С. Нижние оценки сложности поляризованных полиномов над конечными полями // Сибирский математический журнал. 2019. Т. 60, № 1, С. 3–13. https://doi.org/10.33048/smzh.2019.60.101
3. Балюк А. С., Янушковский Г. В. Операторные полиномиальные формы функций над конечными полями // Труды IX Международной конференции "Дискретные модели в теории управляющих систем". М. : МАКС Пресс, 2015. C. 28–30.
4. Berndt B. C., Evans R. J., Williams K. S. Gauss and Jacobi sums. Toronto : John Wiley & Sons Inc., 1998. 600 р.
5. Францева А. С. Сложность представлений булевых функций в классах расширенных двупорожденных операторных форм // Сибирские электронные математические известия. 2019. Т. 16. С. 523–541. https://doi.org/10.33048/semi.2019.16.034
6. Избранные вопросы теории булевых функций / под ред. С. Ф. Винокурова, Н. А. Перязева. М. : Физматлит, 2001. 192 с.
7. Лидл Р., Нидеррайтер Г. Конечные поля : пер. с англ. М.: Мир, 1988. Т. 1. 430 с.
8. Маркелов Н. К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов // Вестник Московского университета. Сер. 15, Вычислительная математика и кибернетика. 2012. Вып. 3, С. 40–45.
9. Muller D. E. Application of Boolean algebra to switching circuit design and to error detection // IRE Trans. Electron. Comput. 1954. Vol. EC3, Issue 3. P. 6–12. https://doi.org/10.1109/IREPGELC.1954.6499441
10. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика. 1995. Т. 34, № 3. C. 323–326.
11. Селезнева С. Н. Верхняя оценка длины функций над конечным полем в классе псевдополиномов // Журнал вычислительной математики и математической физики. 2017. Т. 57, № 5. С. 899–904. https://doi.org/10.7868/S0044466917050118
12. Винокуров С. Ф. Смешанные операторы в булевых функциях и их свойства. Иркутск : Иркутский университет, 2000. 36 с. (Дискретная математика и информатика ; вып. 12).