TC^0 circuits for algorithmic problems in nilpotent groups

DOI10.4230/LIPICS.MFCS.2017.23zbMATH Open1441.68044arXiv1702.06616OpenAlexW2593181919MaRDI QIDQ5111237FDOQ5111237

Armin Weiß, Alexei Myasnikov

Publication date: 26 May 2020

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.

Full work available at URL: https://arxiv.org/abs/1702.06616

Recommendations

• Parallel complexity for nilpotent groups
• Low-complexity computations for nilpotent subgroup problems
• Logspace and compressed-word computations in nilpotent groups
• Algorithmic problems for class-2 nilpotents MR-groups
• Evaluation of circuits over nilpotent and polycyclic groups

zbMATH Keywords

conjugacy problemnilpotent groupsgreatest common divisorsword problemabelian groupssubgroup membership problem\(\mathsf{TC}^0\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Nilpotent groups (20F18) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Word Problems Solvable in Logspace
• Title not available (Why is that?)
• Non-commutative lattice problems
• The Post correspondence problem in groups.
• Logspace and compressed-word computations in nilpotent groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• On homomorphisms onto finite groups
• Symbolic Collection using Deep Thought
• The word problem
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Random nilpotent groups, polycyclic presentations, and Diophantine problems
• Algorithmic meta theorems for circuit classes of constant and logarithmic depth
• Conjugacy in Nilpotent Groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational algorithms for deciding some problems for nilpotent groups
• Evaluating Matrix Circuits
• TC^0 circuits for algorithmic problems in nilpotent groups

Cited In (13)

• Two general schemes of algebraic cryptography
• Low-complexity computations for nilpotent subgroup problems
• Parallel complexity for nilpotent groups
• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
• STACS 2005
• Evaluation of circuits over nilpotent and polycyclic 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
• 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
• Title not available (Why is that?)
• TC^0 circuits for algorithmic problems in nilpotent groups

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)