A lower bound for the computation complexity of a q-ary counter of multiplicity Q in the class of π-circuits
K. L. Rychkov · Journal of Applied and Industrial Mathematics · 2011
A generalization of the concept of parallel-sequential switching circuits (π-circuits) to the case when the variables assigned to contacts can take not two, as in the Boolean case, but a greater number of values. The conductivity of the contact is still two-valued (the contact is either closed or open). A lower bound is obtained on the complexity of these circuits computing the q-ary counter of multiplicity q, i.e., the function φ q : {0, 1, …, q − 1} n → {0, 1} that equals 1 if the sum of values of its variables is a multiple of q.