An upper bound for the complexity of polynomial normal forms of Boolean functions

We consider the problem of minimisation of Boolean functions in the class of polynomial normal forms. We suggest an algorithm for constructing polynomial normal forms for arbitrary Boolean functions such that the length of the obtained formula depends on the number of variables of the function only. As the input of the algorithm, along with the function, we take the solution of a covering problem. The number of elementary conjunctions in the obtained formula is equal to the cardinality of the covering. For the introduced covering problem we find an approximate solution. We succeed to prove that the complexity of Boolean functions in the class of polynomial normal forms is less than $2^{n+1}(\log_2 n + 1)/n$, which allows us to conclude that for almost any Boolean function the complexity of its representation in the polynomial normal form is less than its representation in the disjunctive normal form.