О поиске периодов многочленов Жегалкина

Abstract

Периодом функции алгебры логики $f(x_1, \ldots, x_n)$ называется такой набор $a = (a_1, \ldots, a_n)$ из нулей и единиц, что верно тождество $f(x_1+a_1, \ldots, x_n+a_n) = f(x_1, \ldots, x_n)$. Функция алгебры логики называется периодической, если существует ее ненулевой период. В работе предложен алгоритм, который по многочлену Жегалкина функции алгебры логики $f(x_1, \ldots, x_n)$ находит базис пространства всех ее периодов со сложностью $n^{O(d)}$, где $d$ - степень функции $f$. Как следствие показано, что найти базис пространства всех периодов функции алгебры логики ограниченной степени по ее многочлену Жегалкина можно со сложностью, полиномиальной по числу переменных функции.