TY - GEN
T1 - TC0 circuits for algorithmic problems in nilpotent groups
AU - Myasnikov, Alexei
AU - Weiß, Armin
N1 - Publisher Copyright:
© Alexei Myasnikov and Armin Weiß; licensed under Creative Commons License CC-BY.
PY - 2017/11/1
Y1 - 2017/11/1
N2 - 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.
AB - 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.
KW - Abelian groups
KW - Conjugacy problem
KW - Greatest common divisors
KW - Nilpotent groups
KW - Subgroup membership problem
KW - TC
KW - Word problem
UR - http://www.scopus.com/inward/record.url?scp=85038416676&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85038416676&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2017.23
DO - 10.4230/LIPIcs.MFCS.2017.23
M3 - Conference contribution
AN - SCOPUS:85038416676
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
A2 - Larsen, Kim G.
A2 - Raskin, Jean-Francois
A2 - Bodlaender, Hans L.
T2 - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
Y2 - 21 August 2017 through 25 August 2017
ER -