Lower Bound of the Complexity of Functions over Finite Field of Order 4 in the Class of Polarized Polynomials
The representations, including polynomial, of functions over final fields have been actively investigated. The complexity of such representations is the main stream of research. Polynomial representations of Boolean functions have been studied well enough. The exact values of the complexity have been found for a lot of polynomial classes.
1. Alekseev V.B., Voronenko A.A., Selezneva S.N. On the complexity of representations of k-valued functions by polarized polynomials (in Russian). In proceedings of V International conference «Discrete models in theory of control systems», Ratmino, May 26-29 2003, 2003, pp. 8–9.
2. Baliuk A.S., Yanushkovsky G.V. Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms (in Russian). IIGU Ser. Matematika, 2015, vol. 14, pp. 3–17.
3. Graham R., Knuth D., Patashnik O. Concrete Mathematics. A Foundation for Computer Science. Addison Wesley, 1994. 672 p.
4. Markelov N.K. A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials. Moscow University Computational Mathematics and Cybernetics, 2012, vol. 36, issue 3, pp. 150–154.
5. Peryazev N.A. Complexity of Boolean functions in the class of polarized polynomial forms. Algebra and Logic, 1995, vol. 34, issue 3, pp. 177–179.
6. Selezneva S.N. On the complexity of the representation of functions of manyvalued logics by polarized polynomials. Discrete Mathematics and Applications, 2002, vol. 12, no 3, pp. 229–234.