Collaborative Research: New Algorithms for Group Isomorphism

协作研究：群同构的新算法

• 批准号: 1620484
• 负责人: Joshua Grochow
• 金额: $ 11.16万
• 依托单位: Santa Fe Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-06-15 至 2017-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1620484&HistoricalAwards=false
• 关键词: Collaborative; Research; New; Algorithms; Group

Symmetry reduces large complex systems to manageable quantities of information. Identifying those symmetries and understanding their structure helps to solve a wide range of problems, from improving engineering tasks to disrupting the mechanisms of disease. The century-old problem of deciding whether two sets of symmetries have the same structure is known today as the Group Isomorphism Problem. This problem is fundamental to both computational algebra and computational complexity, and has implications for fields as diverse as material science, particle physics, and chemistry. The primary goal of this project is to develop significantly better approaches to testing isomorphism of finite groups of symmetries. It supports a new multidisciplinary collaboration between researchers at four universities, including students and early-career mathematicians and computer scientists. The Group Isomorphism Problem asks for an algorithm to decide whether two finite groups are equivalent. Both the problem itself, and the techniques designed to improve upon it, have implications for other computational problems, including the better-known problems of Graph Isomorphism and P versus NP. Our team's approach goes beyond existing static recursions such as working sequentially down a derived or lower central series. Using a new dynamic strategy we prioritize the optimal stages of the problem, thereby improving the performance of later stages. To achieve this we are investigating the use of nonassociative rings, spectral sequences, modular representation theory, and p-local cohomology. We are also inspecting recently developed data structures in computational algebra that seem well-suited to our approach, as well as investigating applications to geometric complexity theory.

对称性将大型复杂系统简化为可管理的信息量。识别这些对称性并了解其结构有助于解决从改进工程任务到破坏疾病机制等广泛的问题。决定两组对称性是否具有相同结构的百年问题今天被称为群同构问题。这个问题是计算代数和计算复杂性的基础，并且对材料科学、粒子物理和化学等不同领域都有影响。该项目的主要目标是开发更好的方法来测试有限对称群的同构。它支持四所大学的研究人员之间新的多学科合作，其中包括学生和早期职业数学家和计算机科学家。 群同构问题需要一种算法来确定两个有限群是否等价。该问题本身以及旨在改进该问题的技术都会对其他计算问题产生影响，包括众所周知的图同构问题和 P 与 NP 问题。 我们团队的方法超越了现有的静态递归，例如按顺序向下派生或较低的中心系列进行工作。使用新的动态策略，我们优先考虑问题的最佳阶段，从而提高后续阶段的性能。为了实现这一目标，我们正在研究非结合环、谱序列、模表示理论和 p 局部上同调的使用。我们还在检查最近开发的计算代数数据结构，这些数据结构似乎非常适合我们的方法，并研究在几何复杂性理论中的应用。