License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.23
URN: urn:nbn:de:0030-drops-81089
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8108/
Go to the corresponding LIPIcs Volume Portal

Myasnikov, Alexei ; Weiß, Armin

TC^0 Circuits for Algorithmic Problems in Nilpotent Groups

pdf-format:
LIPIcs-MFCS-2017-23.pdf (0.5 MB)

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.

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 problem of computing greatest common divisors and expressing them as linear combinations.

BibTeX - Entry

@InProceedings{myasnikov_et_al:LIPIcs:2017:8108,
  author =	{Alexei Myasnikov and Armin Wei{\ss}},
  title =	{{TC^0 Circuits for Algorithmic Problems in Nilpotent Groups}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8108},
  URN =		{urn:nbn:de:0030-drops-81089},
  doi =		{10.4230/LIPIcs.MFCS.2017.23},
  annote =	{Keywords: nilpotent groups, TC^0, abelian groups, word problem, conjugacy problem, subgroup membership problem, greatest common divisors}
}

Keywords: nilpotent groups, TC^0, abelian groups, word problem, conjugacy problem, subgroup membership problem, greatest common divisors
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI