Аннотация:
Рассматривается задача о числе нулей булева полинома от $n$ переменных, заданного множеством своих мономов. Предлагается полиномиальный по числу $n$ переменных алгоритм решения этой задачи для “разреженных” полиномов с числом мономов, не превосходящим $C\log_2n$. Найдены общие границы для числа нулей и асимптотические оценки для числа нулей симметрических полиномов.