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.