An Algebraic Approach to Computational Complexity

该项目的知识内容涉及计算复杂性的研究，其目的是了解计算机可以有效地执行哪些任务，而哪些任务最终不能。目前有一个巨大的差距，在非常有限的计算中，最终的限制可以用现有的数学分析，和丰富的任务，如搜索问题的NP-完全，其中的限制目前只是猜测。这个项目涉及到一个新的方法来解决这些问题的基础上隐含的指数模型。这种方法受到量子力学的启发，量子力学用人们熟知的数学，即线性代数来描述物理系统中的转变，但为了做到这一点，它在高维上工作。在这个项目中，计算模型也是指数维的，但它需要在多项式时间内有效地由经典计算机模拟。与量子力学类似，复杂的计算是用很好理解的数学来表示的，即线性和多项式代数，但以高维为代价。正在研究的问题集中在那些能够表示NP完全和#NP完全搜索问题的高维表示是否属于可以在多项式时间内模拟的类别。该方法可以被视为受到量子力学和量子计算启发的代数复杂性理论的一个新分支。从更广泛的影响来看，这项研究的社会影响将取决于其结果。由于主要推动力是对搜索问题的有效算法的新观点，一个积极的结果可能会重新定义在广泛应用的实践中计算的内容。无论结果如何，研究将在一个教育环境中进行，其中包括不断扩大的不同学生、教师、博士后研究员和对计算复杂性的广泛研究领域感兴趣的访问者。

The intellectual content of the project is concerned with the study of computationalcomplexity, which aims at an understanding of which tasks can be effciently performedby computers, and which ultimately cannot. There is currently an enormousgap between the very restricted computations in which the ultimate limitations canbe analysed using existing mathematics, and the rich variety of tasks, such as thesearch 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 implicitlyexponential models. This approach is inspired by quantum mechanics, whichdescribes 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 thisproject the model of computation is also exponential dimensional, but it needs to besimulatable by classical computers effciently in polynomial time. In analogy withquantum mechanics, complex computations are to be expressed in terms of well understoodmathematics, namely linear and polynomial algebra, but at the cost of high dimensions.The questions being investigated center on whether those high dimensionalrepresentations that can express NP-complete and #NP-complete search problemsare 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 onits outcome. Since the main thrust is a new view towards efficient algorithmsfor search problems in general, a positive outcome may redefine what is computedin 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.