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.
