Список выпусков > Серия «Математика». 2017. Том 22
Нижняя оценка сложности поляризованных полиномов семизначных функций
Одним из направлений исследования функций над конечными полями является исследование их представлений, в том числе полиномиальных. При изучении полиномиальных представлений функций можно выделить задачу оценки сложности таких представлений.
Под сложностью реализующего функцию полинома понимается число его ненулевых слагаемых. При этом каждая функция может быть представлена несколькими различными полиномами из одного класса. Под сложностью функции в классе полиномов понимается минимально возможная сложность реализующего ее полинома из этого класса. Под сложностью множества функций в классе полиномов понимается максимально возможная сложность функции из данного множества в классе полиномов.
В случае функций над конечным полем порядка 2 (булевых функций) для многих классов полиномиальных форм известны точные значения сложности таких представлений, а для функций над конечными полями порядка больше двух даже в довольно простых классах полиномов найдены только несовпадающие верхние и нижние оценки сложности.
Данная работа посвящена исследованию представления семизначных функций поляризованными полиномами. Полиномы этого класса имеют вид суммы конечного числа произведений определенного вида.
Для случая булевых и трехзначных функций известны эффективные нижние оценки сложности в классе поляризованных полиномов, а также более слабая мощностная оценка для функций над конечным полем простого порядка.
В предыдущих работах авторами были получены эффективные нижние оценки сложности для случая функций над конечными полями порядка 4 и 5.
В настоящей работе получена эффективная нижняя оценка сложности семизначных функций в классе поляризованных полиномов.
Ссылка для цитирования:
Балюк А.С., Зинченко А.С. Нижняя оценка сложности поляризованных полиномов семизначных функций // Известия Иркутского государственного университета. Серия Математика. 2017. Т. 22. С. 3-17. https://doi.org/10.26516/1997-7670.2017.22.18
1. Алексеев В. Б. О сложности реализации функций k-значной логики поляризованными полиномами / В. Б. Алексеев, А. А. Вороненко, С. Н. Селезнева // Дискретные модели в теории управляющих систем : тр. V Междунар. конф. Ратмино, 26–29 мая 2003 г. – М. : МАКС Пресс, 2003. – C. 8–9.
2. Балюк А. С. Нижняя оценка сложности функций над конечным полем порядка 4 в классе поляризованных полиномов / А. С. Балюк, А. С. Зинченко // Изв. Иркут. гос. ун-та. Сер. Математика. – 2016. – Т. 16. – С. 19–29.
3. Балюк А. С. Нижняя оценка сложности пятизначных функций в классе поляризованных полиномов / А. С. Балюк, А. С. Зинченко // Дискрет. математика. – 2016. – Т. 28, № 4. – С. 29–37.
4. Балюк А. С. Верхние оценки сложности функций над конечными полями в некоторых классах кронекеровых форм / А. С. Балюк, Г. В. Янушковский // Изв. Иркут. гос. ун-та. Сер. Математика. – 2015. – Т. 14. – С. 3–17.
5. Грэхэм Р. Конкретная математика. Основание информатики : пер. с англ. / Р. Грэхем, Д. Кнут, О. Паташник. – М. : Мир, 1998. – 703 с.
6. Казимиров А. С. Верхние оценки сложности функций над непростыми конечными полями в классе поляризованных полиномов / А. С. Казимиров, С. Ю. Реймеров // Изв. Иркут. гос. ун-та. Сер. Математика. – 2016. – Т. 17. – С. 37–45.
7. Маркелов Н. К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов / Н. К. Маркелов // Вестн. Моск. ун-та. Сер. 15, Вычисл. математика и кибернетика. – 2012. – № 3. – С. 40–45.
8. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм / Н. А. Перязев // Алгебра и логика. – 1995. – Т. 34, № 3. – С. 323–326.
9. Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами / С. Н. Селезнева // Дискрет. математика. – 2002. – Т. 14, № 2. – С. 48–53.