×
Bartholdi, Laurent; Figelius, Michael; Lohrey, Markus; Weiß, Armin

Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems. (English) Zbl 07561757

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 29, 29 p. (2020).
Summary: We give lower bounds on the complexity of the word problem of certain non-solvable groups: for a large class of non-solvable infinite groups, including in particular free groups, Grigorchuk’s group and Thompson’s groups, we prove that their word problem is ALOGTIME-hard. For some of these groups (including Grigorchuk’s group and Thompson’s groups) we prove that the circuit value problem (which is equivalent to the circuit evaluation problem) is PSPACE-complete.
For the entire collection see [Zbl 1445.68025].

Cited in 5 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity

Keywords:

\(NC^1\)-hardness; word problem; G-programs; straight-line programs; non-solvable groups; self-similar groups; Thompson’s groups; Grigorchuk’s group
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Ian Agol. The virtual Haken conjecture. Documenta Mathematica, 18:1045-1087, 2013. With an appendix by Ian Agol, Daniel Groves, and Jason Manning. · Zbl 1286.57019
[2] Sanjeev Arora and Boaz Barak. Computational Complexity -A Modern Approach. Cambridge University Press, 2009. doi:10.1017/CBO9780511804090. · Zbl 1193.68112 · doi:10.1017/CBO9780511804090
[3] David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in N C 1 . Journal of Computer and System Sciences, 38(1):150-164, 1989. doi:10.1016/0022-0000(89)90037-8. · Zbl 0667.68059 · doi:10.1016/0022-0000(89)90037-8
[4] David A. Mix Barrington and Denis Thérien. Finite monoids and the fine structure of N C 1 . Journal of the ACM, 35:941-952, 1988. doi:10.1145/48014.63138. · Zbl 0667.68068 · doi:10.1145/48014.63138
[5] Laurent Bartholdi, Michael Figelius, Markus Lohrey, and Armin Weiß. Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems. Technical report, arXiv.org, 2020. arXiv:1909.13781.
[6] Laurent Bartholdi, Rostislav I. Grigorchuk, and Zoran Šuniḱ. Branch groups. In Handbook of algebra, Volume 3, pages 989-1112. Elsevier/North-Holland, Amsterdam, 2003. doi: 10.1016/S1570-7954(03)80078-5. · Zbl 1140.20306 · doi:10.1016/S1570-7954(03)80078-5
[7] Laurent Bartholdi and Volodymyr V. Nekrashevych. Iterated monodromy groups of quadratic polynomials. I. Groups, Geometry, and Dynamics, 2(3):309-336, 2008. doi:10.4171/GGD/42. · Zbl 1153.37379 · doi:10.4171/GGD/42
[8] Martin Beaudry, Pierre McKenzie, Pierre Péladeau, and Denis Thérien. Finite monoids: From word to circuit evaluation. SIAM Journal on Computing, 26(1):138-152, 1997. doi: 10.1137/S0097539793249530. · Zbl 0868.68057 · doi:10.1137/S0097539793249530
[9] L. Bartholdi, M. Figelius, M. Lohrey, and A. Weiß 29:17
[10] Richard Beigel and John Gill. Counting classes: Thresholds, parity, mods, and fewness. Theoretical Computer Science, 103(1):3-23, 1992. doi:10.1016/0304-3975(92)90084-S. · Zbl 0760.68028 · doi:10.1016/0304-3975(92)90084-S
[11] William W. Boone. The Word Problem. Annals of Mathematics, 70(2):207-265, 1959. URL: www.jstor.org/stable/1970103. · Zbl 0102.00902
[12] Daniel P. Bovet, Pierluigi Crescenzi, and Riccardo Silvestri. A uniform approach to define complexity classes. Theoretical Computer Science, 104(2):263-283, 1992. doi:10.1016/ 0304-3975(92)90125-Y. · Zbl 0754.68049 · doi:10.1016/0304-3975(92)90125-Y
[13] John W. Cannon, William J. Floyd, and Walter R. Parry. Introductory notes on Richard Thompson’s groups. L’Enseignement Mathématique, 42(3):215-256, 1996. · Zbl 0880.20027
[14] Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, and Abhi Shelat. The smallest grammar problem. IEEE Transactions on Information Theory, 51(7):2554-2576, 2005. doi:10.1109/TIT.2005.850116. · Zbl 1296.68086 · doi:10.1109/TIT.2005.850116
[15] Max Dehn. Über unendliche diskontinuierliche Gruppen. Mathematische Annalen, 71(1):116-144, 1911. doi:10.1007/BF01456932. · JFM 42.0508.03 · doi:10.1007/BF01456932
[16] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979. · Zbl 0411.68039
[17] Max Garzon and Yechezkel Zalcstein. The complexity of Grigorchuk groups with application to cryptography. Theoretical Computer Science, 88(1):83-98, 1991. doi:10.1016/0304-3975(91) 90074-C. · Zbl 0749.68040 · doi:10.1016/0304-3975(91)90074-C
[18] Rostislav I. Grigorchuk. Burnside’s problem on periodic groups. Functional Analysis and Its Applications, 14:41-43, 1980. doi:10.1007/BF01078416. · Zbl 0595.20029 · doi:10.1007/BF01078416
[19] Rostislav I. Grigorchuk and Zoran Šuniḱ. Asymptotic aspects of Schreier graphs and Hanoi Towers groups. C. R. Math. Acad. Sci. Paris, 342(8):545-550, 2006. doi:10.1016/j.crma. 2006.02.001. · Zbl 1135.20016 · doi:10.1016/j.crma.2006.02.001
[20] Victor S. Guba and Mark V. Sapir. On subgroups of the R. Thompson group F and other diagram groups. Matematicheskii Sbornik, 190(8):3-60, 1999. doi:10.1070/ SM1999v190n08ABEH000419. · Zbl 1095.20021 · doi:10.1070/SM1999v190n08ABEH000419
[21] Narain Gupta and Saïd Sidki. On the Burnside problem for periodic groups. Mathematische Zeitschrift, 182(3):385-388, 1983. doi:10.1007/BF01179757. · Zbl 0513.20024 · doi:10.1007/BF01179757
[22] Frédéric Haglund and Daniel T. Wise. Coxeter groups are virtually special. Advances in Mathematics, 224(5):1890-1903, 2010. doi:10.1016/j.aim.2010.01.011. · Zbl 1195.53055 · doi:10.1016/j.aim.2010.01.011
[23] Ulrich Hertrampf. Über Komplexitätsklassen, die mit Hilfe von k-wertigen Funktionen definiert werden. Habilitationsschrift, Universität Würzburg, 1994.
[24] Ulrich Hertrampf. The shapes of trees. In Proceedings of COCOON 1997, volume 1276 of Lecture Notes in Computer Science, pages 412-421. Springer, 1997. doi:10.1007/BFb0045108. · Zbl 0884.68074 · doi:10.1007/BFb0045108
[25] Ulrich Hertrampf. Algebraic acceptance mechanisms for polynomial time machines. SIGACT News, 31(2):22-33, 2000. doi:10.1145/348210.348215. · doi:10.1145/348210.348215
[26] Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, and Klaus W. Wagner. On the power of polynomial time bit-reductions. In Proceedings of the Eighth Annual Structure in Complexity Theory Conference, pages 200-207. IEEE Computer Society Press, 1993. doi:10.1109/SCT.1993.336526. · doi:10.1109/SCT.1993.336526
[27] Ulrich Hertrampf, Heribert Vollmer, and Klaus Wagner. On balanced versus unbalanced com-putation trees. Mathematical Systems Theory, 29(4):411-421, 1996. doi:10.1007/BF01192696. · Zbl 0853.68097 · doi:10.1007/BF01192696
[28] Derek F. Holt, Markus Lohrey, and Saul Schleimer. Compressed decision problems in hyperbolic groups. In Proceedings of STACS 2019, volume 126 of LIPIcs, pages 37:1-37:16. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2019. URL: http://www.dagstuhl.de/dagpub/ 978-3-95977-100-9. · Zbl 07559146
[29] Derek F. Holt, Sarah Rees, and Claas E. Röver. Groups, Languages and Automata, volume 88 of London Mathematical Society Student Texts. Cambridge University Press, 2017. doi: 10.1017/9781316588246. · Zbl 1515.20012 · doi:10.1017/9781316588246
[30] Birgit Jenner, Pierre McKenzie, and Denis Thérien. Logspace and logtime leaf languages. Information and Computation, 129(1):21-33, 1996. doi:10.1006/inco.1996.0071. · Zbl 0864.68057 · doi:10.1006/inco.1996.0071
[31] C C C 2 0 2 0 29:18 ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems
[32] Howard J. Karloff and Walter L. Ruzzo. The iterated mod problem. Information and Computation, 80(3):193-204, 1989. doi:10.1016/0890-5401(89)90008-4. · Zbl 0671.68013 · doi:10.1016/0890-5401(89)90008-4
[33] Daniel König and Markus Lohrey. Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica, 80(5):1459-1492, 2018. doi:10.1007/s00453-017-0343-z. · Zbl 1390.68311 · doi:10.1007/s00453-017-0343-z
[34] Daniel König and Markus Lohrey. Parallel identity testing for skew circuits with big powers and applications. International Journal of Algebra and Computation, 28(6):979-1004, 2018. doi:10.1142/S0218196718500431. · Zbl 1400.68091 · doi:10.1142/S0218196718500431
[35] Jörg Lehnert and Pascal Schweitzer. The co-word problem for the Higman-Thompson group is context-free. Bulletin of the London Mathematical Society, 39(2):235-241, February 2007. doi:10.1112/blms/bdl043. · Zbl 1166.20025 · doi:10.1112/blms/bdl043
[36] Martin W. Liebeck, Eamonn A. O’Brien, Aner Shalev, and Pham Huu Tiep. The Ore conjecture. Journal of the European Mathematical Society, 12(4):939-1008, 2010. doi:10.4171/JEMS/220. · Zbl 1205.20011 · doi:10.4171/JEMS/220
[37] Yury Lifshits and Markus Lohrey. Querying and embedding compressed texts. In Proceedings of MFCS 2006, volume 4162 of Lecture Notes in Computer Science, pages 681-692. Springer, 2006. doi:10.1007/11821069_59. · Zbl 1132.68379 · doi:10.1007/11821069_59
[38] Richard J. Lipton and Yechezkel Zalcstein. Word problems solvable in logspace. Journal of the Association for Computing Machinery, 24(3):522-526, 1977. doi:10.1145/322017.322031. · Zbl 0359.68049 · doi:10.1145/322017.322031
[39] Markus Lohrey. Leaf languages and string compression. Information and Computation, 209(6):951-965, 2011. doi:10.1016/j.ic.2011.01.009. · Zbl 1221.68138 · doi:10.1016/j.ic.2011.01.009
[40] Markus Lohrey. The Compressed Word Problem for Groups. Springer Briefs in Mathematics. Springer, 2014. doi:10.1007/978-1-4939-0748-9. · Zbl 1391.20003 · doi:10.1007/978-1-4939-0748-9
[41] Volodymyr Nekrashevych. Self-similar groups, volume 117 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2005. doi:10.1090/surv/117. · Zbl 1183.37022 · doi:10.1090/surv/117
[42] Piotr S. Novikov. On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov, pages 1-143, 1955. In Russian. URL: http://mi.mathnet.ru/eng/tm1180.
[43] David Robinson. Parallel Algorithms for Group Word Problems. PhD thesis, University of California, San Diego, 1993.
[44] Joseph J. Rotman. An Introduction to the Theory of Groups (fourth edition). Springer, 1995. · Zbl 0810.20001
[45] Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, 2010. doi:10.1561/0400000039. · Zbl 1205.68175 · doi:10.1561/0400000039
[46] Hans-Ulrich Simon. Word problems for groups and contextfree recognition. In Proceedings of FCT 1979, pages 417-422. Akademie-Verlag, 1979. · Zbl 0413.68044
[47] Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of STOC 1987, pages 77-82. ACM, 1987. doi:10.1145/28395. 28404. · doi:10.1145/28395.28404
[48] Jacques Tits. Free subgroups in linear groups. Journal of Algebra, 20(2):250-270, 1972. doi:10.1016/0021-8693(72)90058-0. · Zbl 0236.20032 · doi:10.1016/0021-8693(72)90058-0
[49] Heribert Vollmer. Introduction to Circuit Complexity. Springer, Berlin, 1999. doi:10.1007/ 978-3-662-03927-4. · Zbl 0967.03035 · doi:10.1007/978-3-662-03927-4
[50] Stephan Waack. The parallel complexity of some constructions in combinatorial group theory. Journal of Information Processing and Cybernetics EIK, 26:265-281, 1990. doi: 10.1007/BFb0029647. · Zbl 0698.68053 · doi:10.1007/BFb0029647
[51] Jan Philipp Wächter and Armin Weiß. An automaton group with pspace-complete word problem. In Proceedings of STACS 2020, volume 154 of LIPIcs, pages 6:1-6:17. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2020. URL: https://www.dagstuhl.de/dagpub/ 978-3-95977-140-5. · Zbl 07650891
[52] John S. Wilson. Embedding theorems for residually finite groups. Mathematische Zeitschrift, 174(2):149-157, 1980. doi:10.1007/BF01293535. · Zbl 0424.20028 · doi:10.1007/BF01293535
[53] Daniel T. Wise. Research announcement: the structure of groups with a quasiconvex hierarchy. Electronic Research Announcements in Mathematical Sciences, 16:44-55, 2009. URL: http: //aimsciences.org//article/id/8d3fc128-8d02-4fee-af67-38001ca1d0ac. · Zbl 1183.20043
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.