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

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

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

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

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

MSC

68Q17

1. Алексеев В. Б. О сложности реализации функций k-значной логики поляризованными полиномами / В. Б. Алексеев, А. А. Вороненко, С. Н. Селезнева // Дискретные модели в теории управляющих систем : тр. V Междунар. конф., Ратмино, 26-29 мая 2003 г. – М. : МАКС Пресс, 2003. – C. 8–9.

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

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

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

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

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