An Algebraic Approach to Computational Complexity

计算复杂性的代数方法

• 批准号: 0310882
• 负责人: Leslie Valiant
• 金额: $ 25万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-07-01 至 2007-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0310882&HistoricalAwards=false
• 关键词: Algebraic; Approach; Computational; Complexity

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.

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