On the complexity of recognizing the completeness of sets of Boolean functions realized by Zhegalkin polynomials

The existence of an algorithm with polynomial time complexity which determines whether a system of Boolean functions realized in the form of Zhegalkin polynomial is complete is proved. It is also proved that if $l$ is the length and $r$ is the rank of the polynomial for a Boolean function, then $l\ge\sqrt{2^r}-1$ for a self-dual function and $l\ge\sqrt{2^r}$ for an even function.