Computational Complexity of Group Theoretic Problems and Graph Isomorphism

群论问题的计算复杂性和图同构

• 批准号: 9013410
• 负责人: Eugene Luks
• 金额: $ 17.54万
• 依托单位: University of Oregon Eugene
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-01-01 至 1994-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9013410&HistoricalAwards=false
• 关键词: Computational; Complexity; Group; Theoretic; Problems

This project concerns the complexity of algebraic problems, concentrating on algorithms for groups and their applications. A major focus is on the development of fast parallel algorithms, but the innovations that are needed for this also seem applicable to sequential algorithms. Another goal is the expansion of the polynomial-time library, especially via new techniques that utilize building blocks such as composition factors and Sylow subgroups. A distinguishing feature of the new methods is an expanding involvement of results that have become available only through recent advances in group theory, particularly the classification of finite simple groups. This is the case even for procedures that underlie new approaches to naive issues such as membership testing. A complementary study focuses on identifying the problems that are likely to remain hard, in either sequential or parallel settings. Almost all of these studies have implications for the problem of testing graph isomorphism.

该项目涉及代数问题的复杂性，重点关注群算法及其应用。 主要焦点是快速并行算法的开发，但所需的创新似乎也适用于顺序算法。 另一个目标是扩展多项式时间库，特别是通过利用组合因子和 Sylow 子群等构建块的新技术。 新方法的一个显着特征是扩大了只有通过群论的最新进展才能获得的结果，特别是有限简单群的分类。 即使对于作为解决简单问题（例如成员资格测试）的新方法的基础的程序也是如此。 一项补充研究的重点是确定在顺序或并行环境中可能仍然难以解决的问题。 几乎所有这些研究都对测试图同构问题有影响。