Properties of polynomials of periodic functions and the complexity of periodicity detection by the Boolean function polynomial

摘要

The algorithmic complexity of periodicity detection of Boolean functions given in a polynomial form is investigated. A function is said to be periodic with period τ if it takes the same values on input strings which differ only by inverting the components corresponding to nonzero entries in the bit string τ. Two polynomial-time algorithms for checking whether a given bit string is a period of a given Boolean function are presented. The relationship between the periods of a function and the length of its polynomial is investigated. The problem of finding the periods is explicitly reduced in polynomial time to the problem of solving a system of Boolean equations.