О свойствах полиномов периодических функций и сложности распознавания периодичности по полиному булевой функции

В статье исследуется вопрос об алгоритмической сложности распознавания периодичности булевых функций, заданных полиномами. Функция называется периодической с периодом $\tau$, если она не изменяется при подстановке вместо всех переменных, соответствующих 1 в векторе $\tau,$ их отрицаний. Построено два полиномиальных алгоритма проверки того, что заданный вектор является периодом булевой функции. Исследована связь периода функции и длины её полинома. Построено в явном виде полиномиальное сведение задачи о поиске периода к решению системы булевых уравнений. Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 13-01-00684.