Article collection "Mathematical Problems of Cybernetics" №4, Moscow, 1992

Authors:Kochergin V.V.

On the complexity of computations in finite Abelian groups

Abstract:

If G is a finite (multiplicitively written) Abelian group, a set of elements B_{G} = {g_{1}, . . . , g_{q}} is called a basis of G if G is the product of the cyclic groups generated by g_{1}, . . . , g_{q}: G = бg_{1}с× . . . × бg_{q}с. Circuits for functional elements of multiplication, which for any two elements of G as input realize their product, are studied. The total number of elements of multiplication in such a circuit S is called the complexity L(S) of S. The complexity of any finite abelian group
G in the basis B_{G} is defined as L(G, B_{G}) = max_{g∈G} min_{S} L(S), where the S are the circuits in the basis B_{G} that realize g. The paper gives proofs of the following estimates as |G| → ∞:
L(G,B_{G}) = (log_{2}|G| / log_{2}log_{2}|G|) (1+O(√ (log_{2}log_{2}log_{2}|G| / log_{2}log_{2}|G|))) +O(p+|B_{G}|)
where p is the largest order of a basis element in B_{G}; and
L(n) = log_{2}n + (1 + o(1))(log_{2}n / log_{2}log_{2}n)
for the corresponding Shannon function L(n) = max_{G:|G|=n}min_{BG}L(G,B_{G}).
En route, some estimates on the complexity of certain auxiliary binary step matrices by gate circuits (rectifier networks) are established.

Keywords:

finite Abelian group, gate circuit (rectifier network), circuit complexity, complexity of group, Shannon function

Kochergin Vadim Vasil'evich, , Механико-математический факультет МГУ, Кафедра дискретной математики, Институт теоретических проблем микромира им. Н. Н. Боголюбова МГУ