Geometry and Complexity Theory

几何与复杂性理论

基本信息

批准号：
1405348
负责人：
Joseph Landsberg
金额：
$ 21.88万
依托单位：
Texas A&M University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2015
资助国家：
美国
起止时间：
2015-09-01 至 2019-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1405348&HistoricalAwards=false
关键词：
Geometry Complexity Theory

项目摘要

Complexity theory addresses both practical and theoretical questions. Practical issues include developing new, efficient algorithms for computations that need to be done frequently (such as multiplying matrices), as well as determining whether more efficient algorithms than the ones already known may exist. The theoretical aspects include questions almost philosophical in nature, such as: Is there really a difference between intuition and systematic problem solving? (This question was asked by Godel and contributed to the development of the famous P versus NP conjecture.) The project will use modern mathematical tools to address these questions, more specifically, algebraic geometry and representation theory. Although the research for this project is driven by questions from computer science, these questions are of interest to mathematics in their own right and have the potential to guide future mathematical research in the way physics has done in recent years.This project focuses on two central questions in complexity theory: the complexity of matrix multiplication and the Geometric Complexity Theory approach to Valiant's conjectures. Regarding matrix multiplication, linear algebra is central to all applications of mathematics, and matrix multiplication is the essential operation of linear algebra. In 1969 Strassen discovered a new algorithm to multiply matrices significantly faster than the standard algorithm. This and subsequent work has led to the astounding conjecture that asymptotically, it is essentially almost as easy to multiply matrices as it is to add them. It is a central question to determine just how efficiently one can multiply matrices, both practically and asymptotically. This project will prove bounds for how efficiently matrices can be multiplied. Regarding Geometric Complexity Theory, a central question in theoretical computer science is whether brute force calculations can be avoided in problems such as the traveling salesman problem. This is the essence of the P versus NP conjecture. The Geometric Complexity Theory (GCT) program addresses such questions using geometric methods. GCT touches on central questions in algebraic geometry, differential geometry, representation theory and combinatorics. The goals of this project are (i) to better establish the mathematical foundations of GCT by solving open problems in combinatorics and classical algebraic geometry and (ii) to solve complexity problems considered more tractable, such as determining whether or not the determinant polynomial admits a small formula.

复杂性理论解决了实用和理论问题。实际问题包括为需要经常完成的计算开发新的，有效的算法（例如，矩阵），以及确定是否比已经知道的更有效算法更有效。理论方面包括本质上几乎哲学上的问题，例如：直觉和系统问题解决之间确实存在区别吗？（Godel提出了这个问题，并为著名的P与NP猜想的发展做出了贡献。）该项目将使用现代的数学工具来解决这些问题，更具体地说，是代数的几何学和代表理论。尽管该项目的研究是由计算机科学的问题驱动的，但这些问题本身对数学感兴趣，并且有可能以物理学近年来的方式指导未来的数学研究。该项目重点介绍了复杂性理论中的两个核心问题：矩阵乘法的复杂性和几何学复杂性的方法对Valiant的猜想方法。关于矩阵乘法，线性代数对于数学的所有应用都是核心，而矩阵乘法是线性代数的必要操作。 1969年，斯特拉森（Strassen）发现了一种新算法，其倍增矩阵的速度明显快于标准算法。这项工作和随后的工作导致了一个惊人的猜想，即渐近地，从本质上讲，矩阵乘以添加它们几乎就像添加它们一样容易。确定实际上和渐近矩阵的有效矩阵的有效效率是一个核心问题。该项目将证明如何将矩阵乘以乘以。关于几何复杂性理论，理论计算机科学中的一个核心问题是，是否可以在旅行推销员问题等问题中避免蛮力计算。这是P与NP猜想的本质。几何复杂性理论（GCT）程序使用几何方法解决了此类问题。 GCT涉及代数几何，差异几何，表示理论和组合学中的中心问题。该项目的目标是（i）通过解决组合学和经典代数几何形状和（ii）的开放问题来更好地建立GCT的数学基础，以解决认为更容易拖延的复杂性问题，例如确定确定性多项式是否可以接受小型公式。