Algorithmic Problems in Group Theory

第一个建议中概述的主要目标也适用于这一新建议：-从电路复杂性和空间复杂性出发，从小复杂性类别的角度，准确地指出群论中算法问题(特别是字问题和共轭问题)的复杂性。在过去的4年里，我们在这方面取得了重大进展。-从更广泛的角度来看，我们希望在德国促进算法群理论领域的发展。第一个有希望的步骤已经取得了。第一点的焦点略有移动：虽然在我们的第一个建议中，重点主要是群的图的图积和基本群(广义Baumlash-Solitar群是一个重要的特例)，但我们计划在接下来的三年里将这一谱扩大到其他重要的类，如自动机群和亚交换群。此外，我们还希望将我们的研究扩展到位于复杂性频谱的更高级别的计算问题：离散优化问题、字方程和压缩字问题。在第一个项目阶段，我们开发了新技术来解决这些问题。我们计划进一步研究这些技术的适用性。

The main objectives outlined in the first proposal also apply to this new proposal:- Pinpointing the complexity of algorithmic problems in group theory (in particular word problems and conjugacy problems) in terms of small complexity classes from circuit complexity and space complexity. Here we made significant progress in the last 4 years.- From a broader perspective we want to promote the field of algorithmic group theory in Germany. First promising steps were already made.The focus for the first point moved slightly: While in our first proposal the emphasis was primarily on graph products and fundamental groups of graphs of groups (with generalized Baumslag-Solitar groups as an important special case), we plan for the next three years to widen this spectrum to other important classes such as automaton groups and metabelian groups. Furthermore, we want to extend our investigations also to computational problems that are located on higher levels of the complexity spectrum: discrete optimization problems, word equations, and compressed word problems. In the first project phase we have developed new techniques in order to tackle these problems. We plan to further investigate the applicability of these techniques.