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-local Cromology的使用。我们还在检查最近开发的计算代数数据结构，这些数据结构似乎非常适合我们的方法，并研究了对几何复杂性理论的应用。