On the complexity of generalized polynomials of k-valued functions
Светлана Николаевна Селезнева, A. B. Dainyak · Moscow University Computational Mathematics and Cybernetics · 2008
Specification of k -valued functions with generalized polynomials (for simple k ) is considered. A generalized polynomial is a mod k polynomial in which each variable may also occur with one or several Post negations. The upper and lower estimates of the complexity of generalized polynomials are found for k -valued functions.