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

A. S. Baliuk

Irkutsk State University, Irkutsk, 664003 Russia

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 $\mathbb F_q$. The value found is equal to $q^{n-1}$. The previously known result for Boolean functions was generalized.

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

UDC: 519.714.4

Received: 18.08.2020

DOI: 10.26907/2541-7746.2020.3.285-299

Bibliographic databases:

•