geometric complexity theory

理论计算机科学和数学交叉的旗舰问题是著名的P vs NP问题。为了解决这个问题，Valiant在1979年提出了一种代数化方法，现在被称为行列式与永久性问题（det vs per）。在2001年Mulmuley和Sohoni重新解释了这个问题的几何和成立几何复杂性理论（GCT），对基本的计算复杂性下界通过代数几何，表示理论和代数组合学的方法。这项建议有两个目标：（1）在GCT的基础上解决基本问题;（2）利用GCT证明显式的复杂度下界。对于目标（1），我们的目标是了解代数自然证明障碍对GCT方法的影响，我们希望将GCT障碍与经典代数复杂性理论中的障碍更紧密地联系起来，并且我们希望了解出现障碍和多重性障碍之间的根本区别，这是两种不同的GCT方法来证明下界。对于目标（2），我们引入了新的方法来度量代数复杂性，这些方法与经典的复杂性度量多项式等价，但具有更好的几何和表示理论。特别是，我们的目标是研究齐次迭代矩阵乘法的复杂性，齐次迹的功率复杂性，边界宽度2 ABP的大小，和边界连续的复杂性。

The flagship problem at the intersection of theoretical computer science and mathematics is the famous P vs NP problem. To work towards its solution in 1979 Valiant introduced an algebraization that is nowadays referred to as the determinant vs permanent problem (det vs per). In 2001 Mulmuley and Sohoni reinterpreted this problem geometrically and founded geometric complexity theory (GCT), an approach towards fundamental computational complexity lower bounds via algebraic geometry, representation theory, and algebraic combinatorics. This proposal has two goals: (1) to settle fundamental questions on the foundations of GCT and (2) to use GCT to prove explicit complexity lower bounds. For goal (1) we aim to understand the impact of the algebraic natural proofs barrier on the GCT approach, we want to relate the GCT conjectures more closely to conjectures in classical algebraic complexity theory, and we want to understand the fundamental difference between occurrence obstructions and multiplicity obstructions, which are two different GCT methods to prove lower bounds. For goal (2) we introduce new ways to measure algebraic complexity that are polynomially equivalent to classical complexity measures, but that have more well-behaved geometry and representation theory. In particular we aim to study the homogeneous iterated matrix multiplication complexity, homogeneous trace of power complexity, border width 2 ABP size, and border continuant complexity.