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

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