geometric complexity theory

点击翻译按钮获取中文摘要

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.