Computation with 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.