|
Известия Иркутского государственного университета. Серия «Математика», 2016, том 16, страницы 19–29
(Mi iigum258)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Нижняя оценка сложности функций над конечным полем порядка 4 в классе поляризованных полиномов
А. С. Балюк, А. С. Зинченко Иркутский государственный университет
Аннотация:
Представления функций над конечными полями, в том числе полиномиальные, в настоящее время активно исследуются. Одним из основных направлений этих исследований является сложность таких представлений. Вопросы полиномиальных представлений булевых функций довольно хорошо изучены. Для многих
классов полиномов найдены точные значения сложности таких представлений.
В последнее время возрос интерес к полиномиальным представлениям функций
над конечными полями порядка больше двух и кольцами вычетов по составному
модулю. Исследование сложности таких представлений сопряжено с определенными
трудностями, и даже в довольно простых классах полиномиальных форм найдены
только несовпадающие верхние и нижние оценки сложности.
В настоящей работе внимание уделено поляризованным полиномам над конечным полем порядка 4. Полиномы этого класса представляют собой суммы произведений множителей определенного вида. Каждый полином реализует некоторую
$n$-местную функцию над конечным полем. Под сложностью полинома понимается число ненулевых слагаемых в нем. Каждая функция может быть реализована
несколькими различными полиномами из одного класса. Под сложностью функции
в классе полиномов понимается минимально возможная сложность реализующего
ее полинома из этого класса.
Ранее были известны эффективные нижние оценки сложности в классе поляризованных полиномов для случая булевых и трехзначных функций и более слабая
мощностная оценка для случая функций над конечным полем простого порядка.
В настоящей статье получена эффективная нижняя оценка сложности функций
над конечным полем порядка 4, аналогичная ранее известным оценкам для булевых
и трехзначных функций.
Ключевые слова:
конечное поле, поляризованный полином, кронекерова форма, нижняя оценка сложности.
Образец цитирования:
А. С. Балюк, А. С. Зинченко, “Нижняя оценка сложности функций над конечным полем порядка 4 в классе поляризованных полиномов”, Известия Иркутского государственного университета. Серия Математика, 16 (2016), 19–29
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/iigum258 https://www.mathnet.ru/rus/iigum/v16/p19
|
Статистика просмотров: |
Страница аннотации: | 145 | PDF полного текста: | 43 | Список литературы: | 26 |
|