TC0 circuits for algorithmic problems in nilpotent groups

Alexei Myasnikov, Armin Weiß

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

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 TC0 - uniformly for all r-generated nilpotent groups of class at most c for fixed r and c. Moreover, if we allow a certain binary representation of the inputs, then the word problem and computation of normal forms is still in uniform TC0, while all the other problems we examine are shown to be TC0-Turing reducible to the problem of computing greatest common divisors and expressing them as linear combinations.

Original languageEnglish
Title of host publication42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
EditorsKim G. Larsen, Jean-Francois Raskin, Hans L. Bodlaender
ISBN (Electronic)9783959770460
DOIs
StatePublished - 1 Nov 2017
Event42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 - Aalborg, Denmark
Duration: 21 Aug 201725 Aug 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume83
ISSN (Print)1868-8969

Conference

Conference42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
Country/TerritoryDenmark
CityAalborg
Period21/08/1725/08/17

Keywords

  • Abelian groups
  • Conjugacy problem
  • Greatest common divisors
  • Nilpotent groups
  • Subgroup membership problem
  • TC
  • Word problem

Fingerprint

Dive into the research topics of 'TC0 circuits for algorithmic problems in nilpotent groups'. Together they form a unique fingerprint.

Cite this