Computation with Finitely Presented Groups

有限呈现群的计算

• 批准号: 1318716
• 负责人: Robert Gilman
• 金额: $ 26.95万
• 依托单位: Stevens Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-15 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1318716&HistoricalAwards=false
• 关键词: Computation; Finitely; Presented; Groups

Intractable computational problems, in particular recursively unsolvable problems, occur naturally in combinatorial group theory and have been studied in that context for over a hundred years. This project is devoted to finding better algorithms and partial algorithms for these problems, both for well-known ones and also for new ones which have arisen, for example, in group-based cryptography. Using techniques developed in their previous work, the investigators will perform computer experiments to discover and test new computational procedures and also to gather information on the distribution of hard instances in specific problems. An algorithm for a computational problem may be useful even though it sometimes fails, if its failures are rare. A well known example is the simplex algorithm for linear optimization. This algorithm (which is used hundreds or thousands of times every day) can take a very long time for certain carefully constructed cases but never does so in practice. In other words the difficult cases are extremely rare. Although there are many other algorithms which behave the same way, this phenomenon is not well understood. The broader significance of this project is that it seeks a better understanding through investigation of an appropriate class of computational problems.

难以解决的计算问题，特别是递归不可解的问题，自然发生在组合群论中，并已在该背景下研究了一百多年。该项目致力于为这些问题找到更好的算法和部分算法，既为众所周知的，也为新出现的，例如，在基于组的密码学。使用在他们以前的工作中开发的技术，研究人员将进行计算机实验，以发现和测试新的计算程序，并收集有关特定问题中硬实例分布的信息。 一个计算问题的算法可能是有用的，即使它有时会失败，如果它的失败是罕见的。一个著名的例子是线性优化的单纯形算法。这种算法（每天使用数百或数千次）可能会花费很长时间来处理某些精心构建的案例，但在实践中从未如此。换句话说，困难的病例非常罕见。虽然有许多其他算法以相同的方式运行，但这种现象并没有得到很好的理解。这个项目的更广泛的意义在于，它通过调查适当的一类计算问题来寻求更好的理解。