Document Open Access Logo

Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems

Authors Laurent Bartholdi , Michael Figelius , Markus Lohrey , Armin Weiß

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.29.pdf
  • Filesize: 0.66 MB
  • 29 pages

Document Identifiers

Author Details

Laurent Bartholdi
  • ENS Lyon, Unité de Mathématiques Pures et Appliquées, France
  • Universität Göttingen, Mathematisches Institut, Germany
Michael Figelius
  • Universität Siegen, Germany
Markus Lohrey
  • Universität Siegen, Germany
Armin Weiß
  • Universität Stuttgart, Institut für Formale Methoden der Informatik (FMI), Germany

Funding

  • Figelius, Michael: Funded by DFG project LO 748/12-1.
  • Lohrey, Markus: Funded by DFG project LO 748/12-1.
  • Weiß, Armin: Funded by DFG project DI 435/7-1.

Acknowledgements

The authors are grateful to Schloss Dagstuhl and the organizers of Seminar 19131 for the invitation, where this work began.

Cite AsGet BibTex

Laurent Bartholdi, Michael Figelius, Markus Lohrey, and Armin Weiß. Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 29:1-29:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.29

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Circuit complexity
  • Mathematics of computing → Combinatorics
Keywords
  • NC^1-hardness
  • word problem
  • G-programs
  • straight-line programs
  • non-solvable groups
  • self-similar groups
  • Thompson’s groups
  • Grigorchuk’s group

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

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. Google Scholar
  2. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: https://doi.org/10.1017/CBO9780511804090.
  3. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹. Journal of Computer and System Sciences, 38(1):150-164, 1989. URL: https://doi.org/10.1016/0022-0000(89)90037-8.
  4. David A. Mix Barrington and Denis Thérien. Finite monoids and the fine structure of NC¹. Journal of the ACM, 35:941-952, 1988. URL: https://doi.org/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. URL: http://arxiv.org/abs/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/10.1137/S0097539793249530.
  9. Richard Beigel and John Gill. Counting classes: Thresholds, parity, mods, and fewness. Theoretical Computer Science, 103(1):3-23, 1992. URL: https://doi.org/10.1016/0304-3975(92)90084-S.
  10. William W. Boone. The Word Problem. Annals of Mathematics, 70(2):207-265, 1959. URL: https://www.jstor.org/stable/1970103.
  11. Daniel P. Bovet, Pierluigi Crescenzi, and Riccardo Silvestri. A uniform approach to define complexity classes. Theoretical Computer Science, 104(2):263-283, 1992. URL: https://doi.org/10.1016/0304-3975(92)90125-Y.
  12. 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. Google Scholar
  13. 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. URL: https://doi.org/10.1109/TIT.2005.850116.
  14. Max Dehn. Über unendliche diskontinuierliche Gruppen. Mathematische Annalen, 71(1):116-144, 1911. URL: https://doi.org/10.1007/BF01456932.
  15. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979. Google Scholar
  16. Max Garzon and Yechezkel Zalcstein. The complexity of Grigorchuk groups with application to cryptography. Theoretical Computer Science, 88(1):83-98, 1991. URL: https://doi.org/10.1016/0304-3975(91)90074-C.
  17. Rostislav I. Grigorchuk. Burnside’s problem on periodic groups. Functional Analysis and Its Applications, 14:41-43, 1980. URL: https://doi.org/10.1007/BF01078416.
  18. 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. URL: https://doi.org/10.1016/j.crma.2006.02.001.
  19. 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. URL: https://doi.org/10.1070/SM1999v190n08ABEH000419.
  20. Narain Gupta and Saïd Sidki. On the Burnside problem for periodic groups. Mathematische Zeitschrift, 182(3):385-388, 1983. URL: https://doi.org/10.1007/BF01179757.
  21. Frédéric Haglund and Daniel T. Wise. Coxeter groups are virtually special. Advances in Mathematics, 224(5):1890-1903, 2010. URL: https://doi.org/10.1016/j.aim.2010.01.011.
  22. Ulrich Hertrampf. Über Komplexitätsklassen, die mit Hilfe von k-wertigen Funktionen definiert werden. Habilitationsschrift, Universität Würzburg, 1994. Google Scholar
  23. Ulrich Hertrampf. The shapes of trees. In Proceedings of COCOON 1997, volume 1276 of Lecture Notes in Computer Science, pages 412-421. Springer, 1997. URL: https://doi.org/10.1007/BFb0045108.
  24. Ulrich Hertrampf. Algebraic acceptance mechanisms for polynomial time machines. SIGACT News, 31(2):22-33, 2000. URL: https://doi.org/10.1145/348210.348215.
  25. 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. URL: https://doi.org/10.1109/SCT.1993.336526.
  26. Ulrich Hertrampf, Heribert Vollmer, and Klaus Wagner. On balanced versus unbalanced computation trees. Mathematical Systems Theory, 29(4):411-421, 1996. URL: https://doi.org/10.1007/BF01192696.
  27. 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.
  28. 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. URL: https://doi.org/10.1017/9781316588246.
  29. Birgit Jenner, Pierre McKenzie, and Denis Thérien. Logspace and logtime leaf languages. Information and Computation, 129(1):21-33, 1996. URL: https://doi.org/10.1006/inco.1996.0071.
  30. Howard J. Karloff and Walter L. Ruzzo. The iterated mod problem. Information and Computation, 80(3):193-204, 1989. URL: https://doi.org/10.1016/0890-5401(89)90008-4.
  31. Daniel König and Markus Lohrey. Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica, 80(5):1459-1492, 2018. URL: https://doi.org/10.1007/s00453-017-0343-z.
  32. 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. URL: https://doi.org/10.1142/S0218196718500431.
  33. 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. URL: https://doi.org/10.1112/blms/bdl043.
  34. 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. URL: https://doi.org/10.4171/JEMS/220.
  35. 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. URL: https://doi.org/10.1007/11821069_59.
  36. Richard J. Lipton and Yechezkel Zalcstein. Word problems solvable in logspace. Journal of the Association for Computing Machinery, 24(3):522-526, 1977. URL: https://doi.org/10.1145/322017.322031.
  37. Markus Lohrey. Leaf languages and string compression. Information and Computation, 209(6):951-965, 2011. URL: https://doi.org/10.1016/j.ic.2011.01.009.
  38. Markus Lohrey. The Compressed Word Problem for Groups. Springer Briefs in Mathematics. Springer, 2014. URL: https://doi.org/10.1007/978-1-4939-0748-9.
  39. Volodymyr Nekrashevych. Self-similar groups, volume 117 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2005. URL: https://doi.org/10.1090/surv/117.
  40. 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.
  41. David Robinson. Parallel Algorithms for Group Word Problems. PhD thesis, University of California, San Diego, 1993. Google Scholar
  42. Joseph J. Rotman. An Introduction to the Theory of Groups (fourth edition). Springer, 1995. Google Scholar
  43. 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. URL: https://doi.org/10.1561/0400000039.
  44. Hans-Ulrich Simon. Word problems for groups and contextfree recognition. In Proceedings of FCT 1979, pages 417-422. Akademie-Verlag, 1979. Google Scholar
  45. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of STOC 1987, pages 77-82. ACM, 1987. URL: https://doi.org/10.1145/28395.28404.
  46. Jacques Tits. Free subgroups in linear groups. Journal of Algebra, 20(2):250-270, 1972. URL: https://doi.org/10.1016/0021-8693(72)90058-0.
  47. Heribert Vollmer. Introduction to Circuit Complexity. Springer, Berlin, 1999. URL: https://doi.org/10.1007/978-3-662-03927-4.
  48. Stephan Waack. The parallel complexity of some constructions in combinatorial group theory. Journal of Information Processing and Cybernetics EIK, 26:265-281, 1990. URL: https://doi.org/10.1007/BFb0029647.
  49. 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.
  50. John S. Wilson. Embedding theorems for residually finite groups. Mathematische Zeitschrift, 174(2):149-157, 1980. URL: https://doi.org/10.1007/BF01293535.
  51. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact