О сложности распознавания полноты множеств булевых функций, реализованных полиномами Жегалкина

Доказано, что существует алгоритм, с полиномиальной временной сложностью определяющий, является ли множество булевых функций, реализованных полиномами Жегалкина, полным. Доказано также, что если числа $l$ и $r$ являются соответственно длиной и рангом полинома cамодвойственной (четной) булевой функции, то верно неравенство $l\ge\sqrt{2^r}-1$ ($l\ge\sqrt{2^r}$).