Complexity lower bound for Boolean functions in the class of extended operator forms

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