Аннотация:
Предложен подход, позволяющий частично обобщить иерархию Грина – Сасао полиномиальных форм булевых функций на случай произвольного конечного поля.
Для сложности псевдокронекеровых и свободно кронекеровых форм $n$-местных функций над произвольным конечным полем $\mathbb F_q$ найдено точное значение функции Шеннона, которое оказывается равным $q^{n-1}$. Работа обобщает ранее известный результат для булевых функций.
Ключевые слова:конечное поле, сложность вычислений, свободно кронекеровы формы, псевдокронекеровы формы.
Полный текст:
PDF файл (660 kB)