On the computational complexity of finite operations (Q2806555)

The question on the complexity of \(k\)-valued functions has been studied by various authors as a contribution to the theory of computation. The present paper deals with two ways of a construction of new functions: subfunctions and implementations; decomposition trees correspond to the first one and ordered decision diagrams correspond to the latter.NEWLINENEWLINELet \(G\) be a transformation group acting on the algebra \(P^n_k\). Then, the authors introduce a \(G\)-equivalence of functions. For various transformation groups \(G\), properties of the equivalence are investigated: the number of the equivalence classes, the cardinality of the classes, a method of a classification of a function, first for a general case.NEWLINENEWLINE The last section of the paper is devoted to Boolean functions \(f\in P_2^n\) (even for \(n\leq 6\), very large cardinalities have been obtained and they had to be calculated on a computer).NEWLINENEWLINEThe text is enriched by a couple of illustrating examples.