Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms.

A polarized polynomial form (PPF) (modulo k) is a modulo k sum of products of variables x₁, . . . , x_n or their Post negations, where the number of negations of each variable is determined by the polarization vector of the PPF. The length of a PPF is the number of its pairwise distinct summands. The length of a function f( x₁, . . . , x_n)of k-valued logic in the class of PPFs is the minimum length among all PPFs realizing the function. The paper presents a sequence of symmetric functions f_n( x₁, . . . , x_n)of three-valued logic such that the length of each function f_n in the class of PPFs is not less than ⌊3 ⁿ⁺¹/4⌋, where ⌊a⌋ denotes the greatest integer less or equal to the number a. The complexity of a system of PPFs sharing the same polarization vector is the number of pairwise distinct summands entering into all of these PPFs. The complexity of a system F ={ f₁,..., f_m} of functions of k-valued logic depending on variables x₁,..., x_n in the class of PPFs is the minimum complexity among all systems of PPFs { p₁,..., p_m}such that all PPFs p₁,..., p_m share the same polarization vector and the PPF p_j realizes the function f_j, j = 1,..., m. Let , where F runs through all systems consisting of m functions of k-valued logic depending on variables x₁,..., x_n. For prime values of k it is easy to derive the estimate . In this paper it is shown that and for all m ≥ 2, n= 1, 2, . . . Moreover, it is demonstrated that the estimates remain valid when consideration is restricted to systems of symmetric functions only. [ABSTRACT FROM AUTHOR]