An Algebraic Approach to Computational Complexity

该项目的智力内容与计算复杂性的研究有关，其目的是了解哪些任务可以由计算机有效地执行，哪些最终不能。目前，在非常有限的计算中，极限可以使用现有的数学进行分析，而各种各样的任务，如NP完全的问题，其中的限制目前只得到验证，这之间存在着巨大的差距。本项目关注的是一种新的方法，这些问题的基础上implicitly指数模型。这种方法的灵感来自量子力学，它描述了物理系统中的过渡方面的理解数学，即线性代数，但为了做到这一点，在高维工作。在这个项目中，计算模型也是指数维的，但它需要在多项式时间内被经典计算机有效地模拟。与量子力学类似，复杂的计算可以用人们熟知的数学来表示，即线性代数和多项式代数，但这是以高维为代价的。研究的问题集中在那些可以表示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.