AF: Small: Geometric Complexity Theory

University Of Chicago, Chicago IL

Investigators

Abstract

Geometric complexity theory is an approach towards the most foundational outstanding conjecture of computer science, P vs. NP, which implies that theorem-proving cannot be automated. Its current focus is on the algebraic variants of this conjecture. The approach was initiated by the PI in projects supported by two earlier NSF grants. It has revealed deep connections between the algebraic variants of the P vs. NP conjecture and foundational problems of algebraic geometry and representation theory, the two fields of mathematics most relevant to this project. The goal of this project is to study, strengthen, and exploit these connections to advance this approach further. The boundary between the tractable and intractable problems in mathematical and physical sciences is defined by the P vs. NP problem. Hence the study undertaken in this project is of central intellectual relevance to computer science, as well as to several other areas of mathematical and physical sciences. Since geometric complexity theory reveals deep connections among the foundational problems of computer science, algebraic geometry, and representation theory, this study may help in bringing these fields together to advance simultaneously on their foundational problems. Effort would also be made to mentor and train post-doctoral researchers in geometric complexity theory, and to disseminate the work in this emerging field through journals, conferences, and workshops. The algebraic variant of the P vs. NP conjecture that this project focuses on is the VP vs. VNP conjecture, which says that the permanent cannot be computed by algebraic circuits of polynomial size and degree. The project supported by the earlier NSF grant CCF-1017760 revealed a foundational difficulty, called the geometric complexity theory chasm, at the interface of algebraic geometry and complexity theory, which needs to be overcome by any realistic approach to this conjecture. This chasm exists because we do not know at present if the complexity class VP is equal to its closure. Hence the most urgent problem in the context of the VP vs. VNP conjecture now is to either show that VP is equal to its closure, or else construct specific candidate families in the closure of VP that are not in VP. This project seeks to investigate this problem using the techniques of geometric complexity theory developed in the earlier project, in conjunction with the advanced techniques of algebraic geometry. The project also seeks to revise the existing geometric complexity theory approach to the VP vs. VNP conjecture, using a refined notion of multiplicity-based obstructions, to take into account the recent negative results. These obstructions are gadgets in algebraic geometry and representation theory that serve as proof certificates of hardness of the permanent. The project will investigate the problem of proving their existence, through a sequence of intermediate problems at the interface of algebraic geometry, representation theory, and complexity theory.