The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields

A.S. Baliuk

Irkutsk State University, Irkutsk, 664003 Russia

E-mail: sacha@hotmail.ru

Received August 18, 2020

Full text PDF

DOI: 10.26907/2541-7746.2020.3.285-299

For citation: Baliuk A.S. The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 285–299. doi: 10.26907/2541-7746.2020.3.285-299. (In Russian)

Abstract

An approach enabling partial generalization of the Green–Sasao hierarchy for polynomial forms of Boolean functions to the case of an arbitrary finite field was introduced.

The exact value of the Shannon function was obtained for the class of pseudo-Kroneker and free-Kronecker forms of n-ary functions over an arbitrary finite field Fq. The value found is equal to qn−1. The previously known result for Boolean functions was generalized.

Keywords: finite field, computational complexity, free-Kronecker forms, pseudo-Kronecker forms

Acknowledgments. The study was supported by the Russian Foundation for Basic Research (project no. 19-01-00200).

References

1. Green D.H. Families of Reed-Muller canonical forms. Int. J. Electron., 1991, vol. 70, no. 2, pp. 259–280. doi: 10.1080/00207219108921277.
2. Sasao T. Representations of logic functions using EXOR operators. In: Representations of Discrete Functions. Boston, Kluwer Acad. Publ., 1996, pp. 29–54. doi: 10.1007/978-1-4613-1385-4 2.
3. Ho P., Perkowski M. Free Kronecker decision diagrams and their application to Atmel 6000 series FPGA mapping. Proc. Conf. on European Design Automation. Grenoble, France, 1994, pp. 8–13. doi: 10.1145/198174.198180.
4. Al-Rabadi A.N. An extended Green-Sasao hierarchy of canonical ternary Galois forms and Universal Logic Modules. Facta Univ., Ser.: Electron. Energ., 2017, vol. 30, no. 1, pp. 49–66. doi: 10.1080/00207219108921277.
5. Izbrannye voprosy teorii bulevykh funktsii [Selected Problems in the Theory of Boolean Functions]. Vinokurov S.F., Peryazev N.A. (Eds.). Moscow, Fizmatlit, 2001. 192 p. (In Russian)
6. Baliuk A.S., Vinokurov S.F. The Shannon function for some classes of operator polynomial forms. Optim., Upr., Intellekt, 2000, vol. 5, no. 1, pp. 111–121. (In Russian)
7. Baliuk A.S., Zinchenko A.S. Lower bounds of complexity for polarized polynomials over finite fields. Sib. Math. J., 2019, vol. 60, no. 1, pp. 1–9. doi: 10.1134/S0037446619010014.
8. Mullen G.L., Panarino D. Handbook of Finite Fields. New York, Chapman and Hall/CRC, 2013. 1068 p. doi: 10.1201/b15006.
9. Baluck A.S., Vinokurov S.F. Classes of operator forms. Proc. 5th Int. Workshop on Boolean Problems. Freiberg, Germany, 2002, pp. 76–83.
10. Peryazev N.A. Complexity of Boolean functions in the class of polarized polynomial forms. Algebra Logic, 1995, vol. 34, no. 3, pp. 177–179. doi: 10.1007/BF02341875.
11. Selezneva S.N. On the complexity of the representation of functions of many-valued logics by polarized polynomials. Discrete Math. Appl., 2002, vol. 12, no. 3, pp. 229–234.
12. Alekseev V.B., Voronenko A.A., Selezneva S.N. On the complexity of realization of functions of a k -valued logic with polarized polynomials. Trudy V Mezhdunar. konferentsii “Diskretnye modeli v teorii upravlyayushchikh sistem” [Poc. 5th Int. Conf. ”Discrete Models in Theory of Control Systems”]. Ratmino, 2003, pp. 8–9. (In Russian)
13. Baliuk A.S., Yanushkovsky G.V. Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms. Izv. Irkutsk. Gos. Univ. Ser. “Mat.”, 2015, no. 14, pp. 3–17. (In Russian)
14. Kazimirov A.S., Reymerov S.Yu. On upper bounds of the complexity of functions over non-prime finite fields in some classes of polarized polynomials. Izv. Irkutsk. Gos. Univ. Ser. “Mat.’, 2016, no. 17, pp. 37–45. (In Russian)
15. Markelov N.K. A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials. Moscow Univ. Comput. Math. Cybern., 2012, vol. 36, no. 3, pp. 150–154. doi: 10.3103/S0278641912030041.
16. Selezneva S.N. On the complexity of k-valued functions in a class of polynomials. Problemy teoreticheskoi kibernetiki: Materialy XVI Mezhdunar. konf. [Problems of Theoretical Cybernetics: Proc. XVI Int. Conf.]. Nizhny Novgorod, 2011, pp. 430–434. (In Russian)
17. Baliuk A.S. On upper bound of the complexity of quasi polynomial representations of functions over finite fields. Izv. Irkutsk. Gos. Univ. Ser. “Mat.”, 2014, no. 10, pp. 3–12. (In Russian)
18. Baliuk A.S. Methods for assessing the complexity of Kronecker forms of functions over finite fields. Trudy X Mezhdunar. konf. “Diskretnye modeli v teorii upravlyayushchikh sistem” [Proc. X Int. Conf. “Discrete Models in the Theory of Control Systems”]. Moscow and Moscow Region, 2018, pp. 46–49. (In Russian)
19. Zierler N. Linear recurring sequences. J. Soc. Ind. Appl. Math., 1959, vol. 7, no. 1, pp. 31–48. doi: 10.1137/0107003.

The content is available under the license Creative Commons Attribution 4.0 License.