Geodesic
Lower bound for the complexity of five-valued polarized polynomials
Diskretnaya Matematika, Tome 28 (2016) no. 4, pp. 29-37 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper is devoted to the complexity of representation of $q$-valued functions by polarized polynomials and by matrix Kronecker forms of certain type. The complexity of a function is the minimal possible number of nonzero coefficients of a polynomial or a Kronecker form representing the function. It is known that for polynomial representation and representation by Kronecker forms of a certain type the maximal values of complexity in the class of all $q$-valued $n$-ary functions coincide. We establish the lower bound of these maximal values for five-valued functions.
Keywords: five-valued functions, polarized polynomial, Kronecker form, complexity lower bounds. 
@article{DM_2016_28_4_a2,
     author = {A. S. Baliuk and A. S. Zinchenko},
     title = {Lower bound for the complexity of five-valued polarized polynomials},
     journal = {Diskretnaya Matematika},
     pages = {29--37},
     year = {2016},
     volume = {28},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_4_a2/}
}
TY  - JOUR
AU  - A. S. Baliuk
AU  - A. S. Zinchenko
TI  - Lower bound for the complexity of five-valued polarized polynomials
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 29
EP  - 37
VL  - 28
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_4_a2/
LA  - ru
ID  - DM_2016_28_4_a2
ER  - 
%0 Journal Article
%A A. S. Baliuk
%A A. S. Zinchenko
%T Lower bound for the complexity of five-valued polarized polynomials
%J Diskretnaya Matematika
%D 2016
%P 29-37
%V 28
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2016_28_4_a2/
%G ru
%F DM_2016_28_4_a2
A. S. Baliuk; A. S. Zinchenko. Lower bound for the complexity of five-valued polarized polynomials. Diskretnaya Matematika, Tome 28 (2016) no. 4, pp. 29-37. http://geodesic.mathdoc.fr/item/DM_2016_28_4_a2/

[1] Peryazev N. A., “Slozhnost bulevykh funktsii v klasse polinomialnykh polyarizovannykh form”, Algebra i logika, 34:3 (1995), 323–326 | MR | Zbl

[2] Selezneva S. N., “O slozhnosti predstavleniya funktsii mnogoznachnykh logik polyarizovannymi polinomami”, Diskretnaya matematika, 14:2 (2002), 48–53 | DOI | MR | Zbl

[3] Markelov N. K., “Nizhnyaya otsenka slozhnosti funktsii trekhznachnoi logiki v klasse polyarizovannykh polinomov”, Vestnik moskovskogo un-ta. Ser. 15, Vychisl. matem. i kibernetika, 2012, no. 3, 40–45 | MR

[4] Alekseev V. B., Voronenko A. A., Selezneva S. N., “O slozhnosti realizatsii funktsii $k$-znachnoi logiki polyarizovannymi polinomami”, Diskretnye modeli v teorii upravlyayuschikh sistem, Trudy V Mezhdunarodnoi konferentsii (Ratmino, 26–29 maya 2003 g.), MAKS Press, M., 2003, 8–9

[5] Balyuk A. S., Yanushkovskii G. V., “Verkhnie otsenki slozhnosti funktsii nad konechnymi polyami v nekotorykh klassakh kronekerovykh form”, Izv. Irkutskogo gos. un-ta. Seriya «Matematika», 14 (2015), 3–17 | Zbl