Group-Theoretic Computation: Complexity and Applications

群论计算：复杂性和应用

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

The research deals with basic computational problems for groups. A central theme involves graph-isomorphism testing and related issues. Polynomial-time results as well as other complexity theoretic issues are being extended to matrix groups, the common domain for applications in the mathematical sciences. Implementation and experimentation is accompanying the theory, and both the permutation-group and new matrix-group methods are being efficiently implemented so that the guaranteed asymptotic timings are retained. The same group-theoretic problems are relevant to a new approach to constraint-satisfaction problems that exploits symmetries and can augment existing applied systems.

这项研究涉及群体的基本计算问题。一个中心主题涉及图形同构测试和相关问题。多项式时间结果以及其他复杂性理论问题正在扩展到矩阵组，这是数学科学中应用的共同领域。实现和实验都伴随着理论，置换群方法和新的矩阵群方法都得到了有效的实现，从而保持了保证的渐近定时。同样的群论问题与一种利用对称性并可以增强现有应用系统的约束满足问题的新方法有关。