Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms
Светлана Николаевна Селезнева · Discrete Mathematics and Applications · 2016
Abstract A polarized polynomial form (PPF) (modulo k ) is a modulo k sum of products of variables x 1 , . . . , 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 1 , . . . , 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 1 , . . . , 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 n +1 /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 L k PPF ( F ) $L_k^{{\rm{PPF}}}(F)$ of a system F ={ f 1 ,..., f m } of functions of k -valued logic depending on variables x 1 ,..., x n in the class of PPFs is the minimum complexity among all systems of PPFs { p 1 ,..., p m }such that all PPFs p 1 ,..., p m share the same polarization vector and the PPF p j realizes the function f j , j = 1,..., m . Let L k PPF ( m , n ) = max F L 2 PPF ( F ) $L_k^{{\rm{PPF}}}(m,n)\, = \,\mathop {\max }\limits_F L_2^{{\rm{PPF}}}(F)$ , where F runs through all systems consisting of m functions of k -valued logic depending on variables x 1 ,..., x n . For prime values of k it is easy to derive the estimate L k PPF ( m , n ) ≤ k n $L_k^{{\rm{PPF}}}(m,n)\, \le \,{k^n}$ . In this paper it is shown that