TC^0 circuits for algorithmic problems in nilpotent groups
From MaRDI portal
Publication:5111237
Abstract: Recently, Macdonald et. al. showed that many algorithmic problems for finitely generated nilpotent groups including computation of normal forms, the subgroup membership problem, the conjugacy problem, and computation of subgroup presentations can be done in Logspace. Here we follow their approach and show that all these problems are complete for the uniform circuit class TC^0 - uniformly for all r-generated nilpotent groups of class at most c for fixed r and c. In order to solve these problems in TC^0, we show that the unary version of the extended gcd problem (compute greatest common divisors and express them as linear combinations) is in TC^0. Moreover, if we allow a certain binary representation of the inputs, then the word problem and computation of normal forms is still in uniform TC^0, while all the other problems we examine are shown to be TC^0-Turing reducible to the binary extended gcd problem.
Recommendations
Cites work
- scientific article; zbMATH DE number 3875506 (Why is no real title available?)
- scientific article; zbMATH DE number 1303030 (Why is no real title available?)
- scientific article; zbMATH DE number 534859 (Why is no real title available?)
- scientific article; zbMATH DE number 1754588 (Why is no real title available?)
- scientific article; zbMATH DE number 1453080 (Why is no real title available?)
- scientific article; zbMATH DE number 3335108 (Why is no real title available?)
- Algorithmic meta theorems for circuit classes of constant and logarithmic depth
- Computational algorithms for deciding some problems for nilpotent groups
- Conjugacy in Nilpotent Groups
- Evaluating matrix circuits
- Logspace and compressed-word computations in nilpotent groups
- Non-commutative lattice problems
- On homomorphisms onto finite groups
- Random nilpotent groups, polycyclic presentations, and Diophantine problems
- Symbolic Collection using Deep Thought
- The Post correspondence problem in groups.
- The word problem
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Word Problems Solvable in Logspace
- \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
Cited in
(15)- Two general schemes of algebraic cryptography
- Low-complexity computations for nilpotent subgroup problems
- Logspace and compressed-word computations in nilpotent groups
- Parallel complexity for nilpotent groups
- The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
- Evaluation of circuits over nilpotent and polycyclic groups
- STACS 2005
- \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
- The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
- The power word problem in graph products
- Batch arguments for \textsf{NP} and more from standard bilinear group assumptions
- Characterizing \(\text{TC}^{0}\) in terms of infinite groups
- Undecidability of the submonoid membership problem for free nilpotent group of class $l\geqslant 2$ of sufficiently large rank
- On the complexity of some problems on groups input as multiplication tables
- scientific article; zbMATH DE number 7561687 (Why is no real title available?)
This page was built for publication: \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111237)
