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

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

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

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

1. Грэхэм Р. Конкретная математика. Основание информатики : пер. с англ. / Р. Грэхэм, Д. Кнут, О. Паташник. – М. : Мир, 1998. – 703 с.

2. Зинченко А. С. Полиномиальные операторные представления функций k-значной логики / А. С. Зинченко, В. И. Пантелеев // Дискрет. анализ и исслед. операций. Сер. 1. – 2006. – Т. 13, № 3. – С. 13–26.

3. Лидл Р. Конечные поля : пер. с англ. / Р. Лидл, Г. Нидеррайтер. – М. : Мир, 1988. – Т. 1. – 430 с.

4. Маркелов Н. К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов / Н. К. Маркелов // Вестн. Моск. ун-та. Сер. 15, Вычисл. математика и кибернетика. – 2012. – № 3. – С. 40–45.

5. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм / Н. А. Перязев // Алгебра и логика. – 1995. – Т. 34, № 3. – С. 323–326.

6. Селезнева С. Н. О сложности задания k-значных функций обобщенно-поляризованными полиномами / С. Н. Селезнева // Дискрет. математика. – 2009. – Т. 21, № 4. – С. 20–29.

7. Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами / С. Н. Селезнева // Дискрет. математика. – 2002. – Т. 14, № 2. – С. 48–53.