https://www.dagstuhl.de/19131

24. – 29. März 2019, Dagstuhl-Seminar 19131

Algorithmic Problems in Group Theory

Organisatoren

Volker Diekert (Universität Stuttgart, DE)
Olga Kharlampovic (The City University of New York, US)
Markus Lohrey (Universität Siegen, DE)
Alexei Myasnikov (Stevens Institute of Technology – Hoboken, US)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 9, Issue 3 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente
Programm des Dagstuhl-Seminars [pdf]

Summary

The field of combinatorial group theory, a part of abstract algebra, is tightly linked to computational problems from its early days. Already in 1911, i.e., 25 years before Turing's work on the halting problem appeared, Max Dehn introduced and investigated three fundamental group theoretical decision problems: the word problem, the conjugacy problem, and the isomorphism problem. Dehn's problems had a strong influence on the development of modern theoretical computer science. It took more that 40 years before the work of Novikov, Boone, Adjan, and Rabin showed the undecidability of Dehn's decision problems in the class of finitely presented groups. Despite these negative results, for many groups the word problem turned out to be decidable in many important classes of groups. With the rise of complexity theory in the 1960's, also the computational complexity of group theoretic problems moved into the focus of research. From the very beginning, this field attracted researchers from mathematics as well as computer science. Using algorithmic techniques from complexity theory, researchers were able to exhibit highly efficient algorithms for groups, where initially only pure decidability results have been known. A milestone in this context is Lipton and Zalcstein's logspace algorithm for the word problem of finitely generated linear groups. This was the first result putting the word problem for an important class of groups into a complexity class below polynomial time. In the last 10 years, researchers pushed the limits further towards small circuit complexity classes. In particular the class TC^0 turned out be very important in this context. Despite its limited computational power many important group theoretical problems problems were shown to be in TC^0.

Complexity theoretical questions are not the only area where we have seen fruitful interactions between group theory and theoretical computer science in recent years. Other examples can be found in automata theory, data compression, model theory, and reachability problems for infinite state systems. The following paragraphs put some of the seminar talks into the context of these topics and mentions some of the open problems that were discussed during the seminar.

Groups and circuit complexity

Howard Straubing gave an excellent survey on circuit complexity that was particularly addressed to non-experts in complexity theory. Barrington's famous result according to which the word problem for every finite non-solvable groups is hard for NC^1 was explained and several important results centered around the circuit complexity class TC^0 were surveyed. In recent years, TC^0 turned out to be the right class for characterizing the complexity of several group theoretical problems. Two seminar talks presented further examples of group theory problems in TC^0: Armin Weiß gave a talk about the power word problem which is a succinct version of the classical word problem, where powers g^n of group elements with binary encoded integer exponents n are allowed in the input. Despite this succinctness, several power word problems (e.g. for nilpotent groups and certain wreath products of finitely generated abelian groups) can be still solved in TC^0. Moses Ganardi talked on the knapsack problem for finitely generated groups which asks for the solvability of certain exponent equations over a group. Among other results he gave a simple proof showing that the knapsack problem for unary encoded integers is in TC^0. This result generalizes to all finitely generated abelian groups.

Several promising open problems related to the circuit complexity of group theoretical problems were discussed in the open problem sessions: The above mentioned result of Barrington on finite non-solvable groups motivates the question whether the word problem for every finitely generated solvable group is NC^1-hard.Also finding new classes of infinite groups with a word problem in TC^0 is an open research problem that was intensively discussed during the seminar. So far, it is known that solvable linear groups have a word problem in TC^0 and that the class of groups with a word problem in TC^0 is closed under wreath products.

Compression techniques in group theory

Compression techniques turned out to be an important tool for obtaining efficient algorithms in group theory. The general philosophy is trying to avoid storing extremely long words by computing on a compressed representation of these words. This led to the formulation of several succinct versions of classical group theoretical problems, where the group elements in the input are given a succinct version. The power word problem that was introduced by Armin Weiß (see the previous paragraph) is such a succinct problem. The main result of Armin Weiß' talk was an efficient reduction of the power word problem for a free group to the (ordinary) word problem of a free group. It is open whether similar reductions also exist for right-angeled Artin groups and hyperbolic groups.

In the context of solving equations over groups and monoids, the so-called recompression technique led to several important results in recent years. Arthur Jez (the inventor of this technique) gave a talk on recompression and outlined his non-deterministic linear time algorithm for solvability of word equations. Ciobanu and Elder presented their recent work on equations in hyperbolic groups where they use recompression in order to show that the set of all solutions for a system of equations over a hyperbolic group is an EDT0L language.

Groups and model theory

This research area directly relates to the previous paragraph. The goal is to understand the first-order theory of groups. Of particular interest is the Diophantine theory. Decidability of the Diophantine theory means that one can decide whether a boolean combination of word equations has a solution. Olga Kharlampovich gave a talk about Diophantine theories of metabelian groups. She proved decidability for several important metabelian groups: Baumslag-Solitar groups BS(1,n) and wreath products mathbb{Z} wr mathbb{Z} and mathbb{Z}_n wr mathbb{Z}. Albert Garreta continued this topic and talked about Diophantine theories of solvable groups. He presented a large class of solvable groups (containing for instance all finitely generated non-virtually abelian nilpotent groups and all polycyclic groups that are not virtually metabelian) for which the Diophantine theory is at least as hard as the Diophantine theory of a suitable ring of algebraic integers. This leads to the conjecture that for each member of his family the Diophantine theory is undecidable.

Montserrat Casals-Ruiz talked on the positive theory of groups acting on trees. The positive theory of a group contains all negation-free statements from the full first-order theory. Montserrat Casals-Ruiz proved that many natural examples of groups acting on trees have the same positive theory as a free group of rank two. Ilya Kazachkov presented new results on the full first-order theory of free products and, more generally, graph products of groups. He showed that under certain conditions, elementary equivalent free products (meaning that their first-order theories coincide) must have elementary equivalent factors.

Groups and automata

Besides complexity of algorithmic problems, a very interesting connection between group theory and theoretical computer science is provided by automata theory, using the very flexible and algorithmically efficient finite state automata to somehow describe an infinite group. This led to the development of automatic groups and automaton groups. Automaton groups are a subclass of so-called self-similar groups. Laurent Bartholdi gave a talk on algorithmic results on self-similar groups and outlined the proof of a recent breakthrough result of Bartholdi and Mitrofanov stating that there exist self-similar groups with an undecidable word problem. For the particular case of automaton groups the word problem belongs to PSPACE. The question whether there exist automaton groups with a PSPACE-complete word problem was intensively discussed during the seminar. Recently, as a direct outcome of the seminar, an automaton group with this property was constructed by Jan Philipp Wächter and Armin Weiß [An automaton group with PSPACE-complete word problem, arXiv, 2019. https://arxiv.org/abs/1906.03424]. Volodia Nekrashevych presented in his talk a generalization of automaton groups based on non-deterministic synchronous automata-transducers and discussed their algorithmic properties and relationship to dynamical systems.

Reachability problems

The study of reachability problems for matrix semigroups has a long tradition in theoretical computer science. Formulated in terms of algebra, the reachability problem is equivalent to the subsemigroup membership problem. Several variants and generalization (rational subset membership problem, knapsack problem) have been recently investigated as well. Igor Potapov gave a survey talk on recent progress on the matrix reachability problem from a computer science perspective. Georg Zetzsche presented several new decidability results for the rational subset membership problem in wreath products. Moses Ganardi talked on wreath products as well, but put the focus on the knapsack problem.

The above talks and the open problem session identified several interersting open problems related to reachability problems. An outstanding open problem in this context asks whether the submonoid membership problem for the group GL_3(mathbb{Z}) is decidable. Recently it was shown that the submonoid membership problem for the Heisenberg group (a subgroup of GL_3(mathbb{Z})) is decidable, This result suggests two generalizations: (i) the rational subset membership problem for Heisenberg groups and (ii) the submonoid membership problem for groups of unitriangular integer matrices. In both case it is open whether the problem is decidable. Georg Zetzsche mentioned in his talk the submonoid membership problem and the rational subset membership problem in the Baumslag-Solitar group BS(1,2) as open research problems.

Concluding remarks and future plans

The seminar was well received as witnessed by the high rate of accepted invitations. There was a good balance between participants from computer science and pure mathematics, and this mixture led to many active discussions and the discovery of new connections and promising open problems. The organizers regard this seminar as a great success. With steadily increasing interactions between such researchers, we foresee another seminar focusing on the interplay between computer science and group theory. Finally, the organizers wish to express their gratitude to the Scientific Directors of the Dagstuhl Centre for their support of the seminar.

Summary text license
  Creative Commons BY 3.0 Unported license
  Volker Diekert, Olga Kharlampovic, Markus Lohrey, and Alexei Myasnikov

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Group theory
  • Circuit complexity
  • Finite automata
  • Algorithms on compressed structures
  • Generic-case complexity

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.