Collaborative Research: New Algorithms for Group Isomorphism

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

• 批准号: 1620454
• 负责人: James Wilson
• 金额: $ 13万
• 依托单位: Colorado State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-06-15 至 2020-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1620454&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-局部上同调的使用。我们还在检查计算代数中最近开发的数据结构，这些数据结构似乎非常适合我们的方法，并调查几何复杂性理论的应用。