KIAM Main page Web Library  •  Publication Searh  Русский 

Article collection "Mathematical Problems of Cybernetics" №4, Moscow, 1992
Authors: Kochergin V.V.
On the complexity of computations in finite Abelian groups
If G is a finite (multiplicitively written) Abelian group, a set of elements BG = {g1, . . . , gq} is called a basis of G if G is the product of the cyclic groups generated by g1, . . . , gq: G = бg1с× . . . × бgqс. 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 BG is defined as L(G, BG) = maxg∈G minS L(S), where the S are the circuits in the basis BG that realize g. The paper gives proofs of the following estimates as |G| → ∞:
L(G,BG) = (log2|G| / log2log2|G|) (1+O(√ (log2log2log2|G| / log2log2|G|))) +O(p+|BG|) where p is the largest order of a basis element in BG; and L(n) = log2n + (1 + o(1))(log2n / log2log2n) for the corresponding Shannon function L(n) = maxG:|G|=nminBGL(G,BG). En route, some estimates on the complexity of certain auxiliary binary step matrices by gate circuits (rectifier networks) are established.
finite Abelian group, gate circuit (rectifier network), circuit complexity, complexity of group, Shannon function
Publication language: russian,  pages: 40 (p. 178-217)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Kochergin Vadim Vasil'evich,  ,  Механико-математический факультет МГУ, Кафедра дискретной математики, Институт теоретических проблем микромира им. Н. Н. Боголюбова МГУ