On the complexity of computation in finite Abelian, nilpotent and soluble groups. (English. Russian original) Zbl 0840.20013
Discrete Math. Appl. 3, No. 3, 297-319 (1993); translation from Diskretn. Mat. 5, No. 1, 91-111 (1993).
This article was originally published in Russian in Diskretn. Mat. The translation was done by the author himself. It continues the author’s investigations done [in Dokl. Akad. Nauk SSSR 317, No. 2, 291-294 (1991; Zbl 0756.20009), summary from Mat. Vopr. Kibern. 4, 178-217 (1992; Zbl 0828.20040)].
From the author’s abstract: The problem of computation of finite group elements by means of one operation, multiplication, is considered, when an arbitrary set of generators is given. Schemes of functional elements […]are used as a computation model […]. For a functional characterizing computation complexity in the finite soluble group over an arbitrary set of generators [an]asymptotically tight value is obtained under some restrictions. For the Shannon functions, characterizing computation complexity in all Abelian (nilpotent) groups of order \(n\), asymptotically tight (tight in order) values re obtained.
One should note that not the complexity of multiplication of two arbitrary group elements on a computer, but the number of multiplications required to construct an arbitrary group element out of the group generators, is investigated. Thus actually boundaries for the maximum over all group elements of the minimal length of a word describing it as a product of any given group generators are found.
From the author’s abstract: The problem of computation of finite group elements by means of one operation, multiplication, is considered, when an arbitrary set of generators is given. Schemes of functional elements […]are used as a computation model […]. For a functional characterizing computation complexity in the finite soluble group over an arbitrary set of generators [an]asymptotically tight value is obtained under some restrictions. For the Shannon functions, characterizing computation complexity in all Abelian (nilpotent) groups of order \(n\), asymptotically tight (tight in order) values re obtained.
One should note that not the complexity of multiplication of two arbitrary group elements on a computer, but the number of multiplications required to construct an arbitrary group element out of the group generators, is investigated. Thus actually boundaries for the maximum over all group elements of the minimal length of a word describing it as a product of any given group generators are found.
Reviewer: M.Weller (Essen)
MSC:
| 20D10 | Finite solvable groups, theory of formations, Schunck classes, Fitting classes, \(\pi\)-length, ranks |
| 20D15 | Finite nilpotent groups, \(p\)-groups |
| 20F05 | Generators, relations, and presentations of groups |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
