Аннотация:
В работе предлагается такой алгоритм на основе свойств матрицы мономов. Для различных типов полиномов приведены точные формулы числа нулей полинома и матожидания числа нулей. Рассматривается подкласс булевых полиномов — полиномы с разделяющимися переменными. Доказан результат, который может рассматриваться как обобщение леммы о рандомизации. Теоретические результаты работы могут служить основой методик оценки применимости полиномов в различных прикладных задачах. Библ. 6.
Ключевые слова:булев полином, корни полинома, $NP$-трудные задачи, лемма о рандомизации.
Список литературы