Верхняя оценка сложности полиномиальных нормальных форм булевых функций

Рассматривается задача минимизации булевых функций в классе полиномиальных нормальных форм. Предлагается алгоритм построения полиномиально нормальных форм для произвольных булевых функций, причем длина полученной формулы зависит только от числа переменных функции. В качестве исходной информации для алгоритма, помимо функции, используется решение одной задачи о покрытии. При этом число элементарных конъюнкций в полученной формуле равно мощности покрытия. Для введенной задачи о покрытии найдено приближенное решение. В итоге удалось доказать, что сложность булевых функций в классе полиномиальных нормальных форм меньше чем $2^{n+1}(\log_2n+1)/n$. Это позволяет сделать вывод о том, что для почти всех булевых функций их сложность при представлении в виде полиномиальных нормальных форм меньше чем при представлении в виде дизъюнктивных нормальных форм.