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.