The intellectual content of the project is concerned with the study of computational complexity, which aims at an understanding of which tasks can be effciently performed by computers, and which ultimately cannot. There is currently an enormous gap between the very restricted computations in which the ultimate limitations can be analysed using existing mathematics, and the rich variety of tasks, such as the search problems that are NP-complete, where the limitations are currently only conjectured. This project is concerned with a new approach to these problems based on implicitly exponential models. This approach is inspired by quantum mechanics, which describes the transitions in physical systems in terms of well understood mathematics, namely linear algebra, but in order to do so works in high dimensions. In this project the model of computation is also exponential dimensional, but it needs to be simulatable by classical computers effciently in polynomial time. In analogy with quantum mechanics, complex computations are to be expressed in terms of well understood mathematics, namely linear and polynomial algebra, but at the cost of high dimensions. The questions being investigated center on whether those high dimensional representations that can express NP-complete and #NP-complete search problems are within the class that can be simulated in polynomial time. The approach can be viewed as a new branch of algebraic complexity theory that is inspired by quantum mechanics and quantum computation.
With regard to broader impacts the societal impact of the research will depend on its outcome. Since the main thrust is a new view towards efficient algorithms for search problems in general, a positive outcome may redefine what is computed in practice across a wide range of applications. Whatever the outcome the research will be carried out in an educational environment that includes an expanding group of diverse students, faculty, postdoctoral fellows and visitors with interests in the broad research area of computational complexity.
