Вычисление булевых функций многочленами

В работе рассматривается такой тип вычисления булевой функции с помощью многочлена как представление с помощью знака. Это означает, что знак многочлена согласуется со значением функции на любом входе. Цель этой работы – изучение методов, связанных с такими представлениями, и их применение для получения новых теорем. В основном, это оценки на степень и разреженность многочленов. Моя стратегия в этом исследовании заключается в том, чтобы подробно изучить функцию Parity и отталкиваться от результатов, полученных для этой функции. Для знаковой репрезентации это в некотором смысле особенная функция. Она представима только с помощью многочленов большой степени и разреженности, но при этом её значение не зависит от порядка переменных. Эта особенность позволила разработать интересные методы получения оценок на примере этой функции. В итоге наиболее сложные и красивые теоремы не получилось перенести на другие функции. Но получилось обобщить теорему, которая позволяет получить верхние оценки на степень и разреженность многочлена для репрезентации функции Parity над любым множеством целых неотрицательных чисел. Этот результат получилось перенести на другие функции и построить конструкцию, которая позволяет сделать то же самое для любой булевой функции.