Algorithmic Problems in Group Theory

群论中的算法问题

• 批准号: 288360912
• 负责人: Professor Dr. Markus Lohrey
• 金额: --
• 依托单位: Department Elektrotechnik und Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2016
• 资助国家: 德国
• 起止时间: 2015-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/288360912?language=en
• 关键词: Algorithmic; Problems; 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.

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