Algorithmic Problems in Group Theory

在第一个建议中概述的主要目标也适用于这个新的建议：-精确定位复杂性的算法问题在群论（特别是字的问题和共轭问题）方面的小复杂性类电路复杂性和空间复杂性。 在过去的四年里，我们在这方面取得了重大进展。从更广泛的角度来看，我们希望促进算法群论领域的发展， 德国。第一个有希望的步骤已经完成。第一点的焦点略有移动：虽然在我们的第一个提案中，重点主要是图积和群的图的基本群（广义鲍姆斯拉格-索利塔群作为一个重要的特殊情况），但我们计划在未来三年内将这一范围扩大到其他重要类别，例如自动机群和元阿贝尔群。此外，我们还希望将我们的调查扩展到位于复杂度谱的更高级别的计算问题：离散优化问题，单词方程和压缩单词问题。在项目的第一阶段，我们开发了新技术来解决这些问题。我们计划进一步研究这些技术的适用性。

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.