А. С. Балюк, А. С. Зинченко, “Нижние оценки сложности поляризованных полиномов над конечными полями”, Сиб. матем. журн., 2019, том 60, номер 1,страницы 3

Эта публикация цитируется в 3 статьях

Нижние оценки сложности поляризованных полиномов над конечными полями

А. С. Балюк^a, А. С. Зинченко^b

^a ООО «Информатика медицины», ул. Рабочая, 2а/4, оф. 409, Иркутск 66401
^b Иркутский гос. университет, бул. Гагарина, 20, Иркутск 66400

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

Ключевые слова: нижняя оценка сложности, поляризованный полином, конечное поле.

УДК: 519.714.4

Статья поступила: 19.04.2018
Окончательный вариант: 19.04.2018
Принята к печати: 17.08.2018

DOI: 10.33048/smzh.2019.60.101