TY - JOUR
T1 - Parallel complexity for nilpotent groups
AU - Myasnikov, Alexei
AU - Weiß, Armin
N1 - Publisher Copyright:
© 2022 World Scientific Publishing Company.
PY - 2022/8/1
Y1 - 2022/8/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 - even if an r-generated nilpotent group of class at most c is part of the input but r and c are fixed constants. In particular, unary encoded systems of a bounded number of linear equations over the integers can be solved in TC0. In order to solve these problems in TC0, we show that the unary version of the extended gcd problem (compute greatest common divisors and express them as linear combinations) is in TC0. 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 binary extended gcd problem.
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 - even if an r-generated nilpotent group of class at most c is part of the input but r and c are fixed constants. In particular, unary encoded systems of a bounded number of linear equations over the integers can be solved in TC0. In order to solve these problems in TC0, we show that the unary version of the extended gcd problem (compute greatest common divisors and express them as linear combinations) is in TC0. 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 binary extended gcd problem.
KW - Nilpotent groups
KW - T C 0
KW - greatest common divisors
KW - subgroup membership
UR - http://www.scopus.com/inward/record.url?scp=85129122289&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85129122289&partnerID=8YFLogxK
U2 - 10.1142/S0218196722500382
DO - 10.1142/S0218196722500382
M3 - Article
AN - SCOPUS:85129122289
SN - 0218-1967
VL - 32
SP - 895
EP - 928
JO - International Journal of Algebra and Computation
JF - International Journal of Algebra and Computation
IS - 5
ER -