Parallel complexity for nilpotent groups. (English) Zbl 1509.20051
Summary: Recently, J. Macdonald et al. [Trans. Am. Math. Soc. 375, No. 8, 5425–5459 (2022; Zbl 1515.20157)] 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 \(\mathsf{LOGSPACE}\). Here, we follow their approach and show that all these problems are complete for the uniform circuit class \(\mathsf{TC}^0\) – 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 \(\mathsf{TC}^0\). In order to solve these problems in \(\mathsf{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 \(\mathsf{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 \(\mathsf{TC}^0\), while all the other problems we examine are shown to be \(\mathsf{TC}^0\)-Turing-reducible to the binary extended gcd problem.
MSC:
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 20F18 | Nilpotent groups |
| 68Q25 | Analysis of algorithms and problem complexity |
Citations:
Zbl 1515.20157References:
| [1] | Blackburn, N., Conjugacy in nilpotent groups, Proc. Amer. Math. Soc.16(1) (1965) 143-148. · Zbl 0127.01302 |
| [2] | Boone, W. W., The word problem, Ann. of Math.70(2) (1959) 207-265. · Zbl 0102.00902 |
| [3] | Dehn, M., Über unendliche diskontinuierliche Gruppen, Math. Ann.71(1) (1911) 116-144. · JFM 42.0508.03 |
| [4] | B. Eick and D. Kahrobaei, Polycyclic groups: A new platform for cryptology?, preprint (2004), arXiv:math/0411077. |
| [5] | Elberfeld, M., Jakoby, A. and Tantau, T., Algorithmic meta theorems for circuit classes of constant and logarithmic depth, Electron. Colloq. Comput. Complex.18 (2011) 128. · Zbl 1245.68086 |
| [6] | Garreta, A., Miasnikov, A. and Ovchinnikov, D., Random nilpotent groups, polycyclic presentations, and Diophantine problems, Groups Complex. Cryptol.9(2) (2017) 99-115. · Zbl 1378.20049 |
| [7] | Hall, P., The Edmonton Notes on Nilpotent Groups, (Queen Mary College, London, 1969). |
| [8] | Hesse, W., Division is in uniform TC(ˆ0), in Proc. 28th Int. Colloquium Automata, Languages and Programming, eds. Orejas, F., Spirakis, P. G. and van Leeuwen, J., , Vol. 2076 (Springer, 2001), pp. 104-114. · Zbl 0967.00069 |
| [9] | Hesse, W., Allender, E. and Barrington, D. A. M., Uniform constant-depth threshold circuits for division and iterated multiplication, J. Comput. Syst. Sci.65 (2002) 695-716. · Zbl 1059.68044 |
| [10] | Kargapolov, M. I. and Merzljakov, J. I., Fundamentals of the Theory of Groups, , Vol. 62 (Springer-Verlag, New York, 1979). Translated from the second Russian edition by Robert G. Burns. · Zbl 0549.20001 |
| [11] | Kargapolov, M. I., Remeslennikov, V. N., Romanovskii, N. S., Roman’kov, V. A. and Čurkin, V. A., Algorithmic questions for \(\sigma \)-powered groups, Algebra Log.8 (1969) 643-659. · Zbl 0238.20050 |
| [12] | König, D. and Lohrey, M., Evaluating matrix circuits, in Computing and Combinatorics, , Vol. 9198 (Springer, Cham, 2015), pp. 235-248. · Zbl 1386.68061 |
| [13] | Lange, K. and McKenzie, P., On the complexity of free monoid morphisms, in Proc. 9th Int. Symp. Algorithms and Computation, eds. Chwa, K. and Ibarra, O. H., , Vol. 1533 (Springer, 1998), pp. 247-256. · Zbl 0930.68081 |
| [14] | Laue, R., Neubüser, J. and Schoenwaelder, U., Algorithms for finite soluble groups and the SOGOS system, in Computational Group Theory (Academic Press, London, 1984), pp. 105-135. · Zbl 0547.20012 |
| [15] | Leedham-Green, C. R. and Soicher, L. H., Symbolic collection using deep thought, LMS J. Comput. Math.1 (1998) 9-24(electronic). · Zbl 0924.20029 |
| [16] | Lipton, R. J. and Zalcstein, Y., Word problems solvable in logspace, J. ACM24 (1977) 522-526. · Zbl 0359.68049 |
| [17] | Lohrey, M. and Weiß, A., The power word problem, in Proc. 44th Int. Symp. on Mathematical Foundations of Computer Science, , Vol. 138 (Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2019), pp. 43:1-43:15. · Zbl 1542.20137 |
| [18] | Macdonald, J., Miasnikov, A. and Ovchinnikov, D., Low-complexity computations for nilpotent subgroup problems, Int. J. Algebra Comput.29(4) (2019) 639-661. · Zbl 1515.20156 |
| [19] | J. Macdonald, A. G. Myasnikov, A. Nikolaev and S. Vassileva, Logspace and compressed-word computations in nilpotent groups, Trans. Amer. Math. Soc. (2022) To appear. http://arxiv.org/abs/1503.03888. |
| [20] | Majewski, B. S. and Havas, G., The complexity of greatest common divisor computations, in Algorithmic Number Theory, , Vol. 877 (Springer, Berlin, 1994), pp. 184-193. · Zbl 0834.68050 |
| [21] | A. Mal’cev, On homomorphisms onto finite groups, Amer. Math. Soc.119 (1983) 67-79. Translation from Uch. Zap. Ivanov. Gos. Pedagog Inst.18 (1958) 49-60. · Zbl 0511.20026 |
| [22] | Miasnikov, A., Vassileva, S. and Weiß, A., The conjugacy problem in free solvable groups and wreath products of abelian groups is in TC^0, Theory Comput. Syst.63(4) (2019) 809-832. · Zbl 1453.20045 |
| [23] | Mostowski, A., Computational algorithms for deciding some problems for nilpotent groups, Fund. Math.59(2) (1966) 137-152. · Zbl 0143.03702 |
| [24] | Myasnikov, A., Nikolaev, A. and Ushakov, A., The Post correspondence problem in groups, J. Group Theory17(6) (2014) 991-1008. · Zbl 1315.20035 |
| [25] | Myasnikov, A., Nikolaev, A. and Ushakov, A., Non-commutative lattice problems, J. Group Theory19(3) (2016) 455-475. · Zbl 1392.20028 |
| [26] | Myasnikov, A. G. and Weiß, A., TC^0 circuits for algorithmic problems in nilpotent groups, in Proc. 42nd Int. Symp. Mathematical Foundations of Computer Science (Schloss Dagstuhl — Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2017), pp. 23:1-23:14. · Zbl 1441.68044 |
| [27] | Novikov, P. S., On the algorithmic unsolvability of the word problem in group theory, Trudy Mat. Inst. Steklov44 (1955) 1-143. in Russian. |
| [28] | G. Ostheimer, Personal communication (2019). |
| [29] | D. Robinson, Parallel Algorithms for Group Word Problems, PhD thesis, University of California, San Diego (1993). |
| [30] | Sedjelmaci, S. M., Two fast parallel GCD algorithms of many integers, in Proc. 2017 ACM on Int Symp Symbolic and Algebraic Computation, eds. Burr, M. A., Yap, C. K. and Din, M. S. E. (ACM, 2017), pp. 397-404. · Zbl 1457.11172 |
| [31] | Segal, D., Polycyclic Groups, , Vol. 82 (Cambridge University Press, Cambridge, 1983). · Zbl 0516.20001 |
| [32] | Sims, C. C., Computation with Finitely Presented Groups, , Vol. 48 (Cambridge University Press, Cambridge, 1994). · Zbl 0828.20001 |
| [33] | Vollmer, H., Introduction to Circuit Complexity (Springer, Berlin, 1999). · Zbl 0931.68055 |
| [34] | Warfield, R. B. Jr., Nilpotent Groups, , Vol. 513 (Springer-Verlag, Berlin, New York, 1976). · Zbl 0347.20018 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
