The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear (Q357917)

This paper studies the circuit complexity of checking the properties of Boolean and multivalued functions. In fact, the problem of checking polynomiality of \(k\)-valued logic functions is considered. The author considers in detail the case of an arbitrary composite \(k\). An algorithm is described that, by the vector of values of \(k\)-valued logic functions \(f(x_1,\dots,x_n)\), checks whether this function can be represented by a polynomial modulo \(k\) and, if the answer is positive, then one of its polynomials is constructed.