Эта публикация цитируется в
3 статьях
О поиске периодов многочленов Жегалкина
С. Н. Селезнева МГУ имени М. В. Ломоносова
Аннотация:
Периодом функции алгебры логики
$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$. Как следствие показано, что найти базис пространства всех периодов функции алгебры логики ограниченной степени по ее многочлену Жегалкина можно со сложностью, полиномиальной по числу переменных функции.
Ключевые слова:
функция алгебры логики (булева функция), многочлен Жегалкина, периодичность, линейная структура, алгоритм, сложность.
УДК:
519.712.3
Статья поступила: 17.06.2021
DOI:
10.4213/dm1658