Geodesic
An upper bound for the complexity of polynomial normal forms of Boolean functions
Diskretnaya Matematika, Tome 17 (2005) no. 3, pp. 80-88
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{DM_2005_17_3_a7,
     author = {K. D. Kirichenko},
     title = {An upper bound for the complexity of polynomial normal forms of {Boolean} functions},
     journal = {Diskretnaya Matematika},
     pages = {80--88},
     year = {2005},
     volume = {17},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2005_17_3_a7/}
}
TY  - JOUR
AU  - K. D. Kirichenko
TI  - An upper bound for the complexity of polynomial normal forms of Boolean functions
JO  - Diskretnaya Matematika
PY  - 2005
SP  - 80
EP  - 88
VL  - 17
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2005_17_3_a7/
LA  - ru
ID  - DM_2005_17_3_a7
ER  - 
%0 Journal Article
%A K. D. Kirichenko
%T An upper bound for the complexity of polynomial normal forms of Boolean functions
%J Diskretnaya Matematika
%D 2005
%P 80-88
%V 17
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2005_17_3_a7/
%G ru
%F DM_2005_17_3_a7
K. D. Kirichenko. An upper bound for the complexity of polynomial normal forms of Boolean functions. Diskretnaya Matematika, Tome 17 (2005) no. 3, pp. 80-88. http://geodesic.mathdoc.fr/item/DM_2005_17_3_a7/

[1] Vinokurov S. F., Peryazev N. A., “Polinomialnye razlozheniya bulevykh funktsii”, Kibernetika i sistemnyi analiz, 6 (1993), 34–47 | MR | Zbl

[2] Korshunov A. D., “O slozhnosti kratchaishikh diz'yunktivnykh normalnykh form sluchainykh bulevykh funktsii”, Metody diskretnogo analiza v optimizatsii upravlyayuschikh sistem, 40 (1983), 25–53 | MR | Zbl

[3] Kuznetsov S. E., “O nizhnei otsenke dliny kratchaishei d.n.f. pochti vsekh bulevykh funktsii”, Veroyatnostnye metody i kibernetika, 19 (1983), 44–47 | MR | Zbl

[4] Peryazev N. A., Osnovy teorii bulevykh funktsii, Fizmatlit, Moskva, 1999

[5] Even S., Kohavi I., Paz A., “On minimal modulo 2 sums of products for switching functions”, IEEE Trans. Elect. Comput., 1967, 671–674 | DOI | Zbl

[6] Koda N., Sasao T., “An upper bound on the number of products in minimum ESOPs”, Representations of discrete functions, eds. Sasao T., Fujita M., Kluwer, Boston, 1996, 94–101