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

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

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

В данной работе получены верхние оценки для функций над полями порядков 2^k и p^k, где p — простое и p ⩾ 3.

MSC

68Q17

1. Балюк А. С. Верхние оценки сложности функций над конечными полями в некоторых классах кронекеровых форм / А. С. Балюк, Г. В. Янушковский // Изв. Иркут. гос. ун-та. Сер. Математика. – 2015. – Т. 14. – С. 3–17.

2. Балюк А. С. Нижняя оценка сложности функций над конечным полем порядка 4 в классе поляризованных полиномов / А. С. Балюк, А. С. Зинченко // Изв. Иркут. гос. ун-та. Сер. Математика. – 2016. – Т. 16. – С. 19–29.

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

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

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

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

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

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

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