scientific article; zbMATH DE number 18644
\(HNN\)-extensions\(NC^ 1\)- equivalentalgorithmsdepthfinitely presented groupfree and direct productsparallel complexityword problemwreath products
Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)
[For the entire collection see Zbl 0731.00026.] The paper presents some nice ideas of how to parallelize known algorithms to solve the word problem for some important classes of groups. To be more precise, the parallel complexity of some group constructions --- such as free and direct products, special \(HNN\)-extensions and wreath products --- is studied. So the question is as follows: Suppose the finitely presented group \(G\) is built from \(H\) and \(K\) by one of the above mentioned constructions and suppose the parallel complexities of \(H\) and \(K\) are known. What can be said about the parallel complexity of \(G\)? Here is one typical result: Let \(G\) be the wreath product of \(H\) and \(K\). Then the word problem of \(G\) is \(NC^ 1\)-equivalent to the maximal complexity of \(H\) and \(K\). Here \(NC^ 1\) is the set of functions \(f: \{0,1\}^*\to\{0,1\}^*\) computable by a uniform Boolean circuit family \(<\alpha_ n>_{n\in N}\) in which \(\alpha_ n\) has size polynomial in \(n\) and depth \(O(\hbox{log} n)\).
- Complexity, combinatorial group theory and the language of palutators
- Parallel poly-pushdown groups
- The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
- The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\)
- scientific article; zbMATH DE number 4145340 (Why is no real title available?)
- The Parallel Complexity of Abelian Permutation Group Problems
- On the parallel complexity of linear groups
- Parallel algorithms for power circuits and the word problem of the Baumslag group
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976049)
