AF: Small: Geometric Complexity Theory

几何复杂性理论是对计算机科学中最基础的杰出猜想P vs. NP的一种方法，这意味着定理证明不能自动化。它目前的重点是这个猜想的代数变体。该方法是由PI在两个早期NSF资助的项目中发起的。它揭示了P与NP猜想的代数变体与代数几何和表示理论的基础问题之间的深刻联系，这两个数学领域与该项目最相关。该项目的目标是研究、加强和利用这些联系，进一步推进这种方法。在数学和物理科学中，易于处理和难以处理的问题之间的界限是由P与NP问题定义的。因此，在这个项目中进行的研究是与计算机科学以及数学和物理科学的其他几个领域的核心知识相关。由于几何复杂性理论揭示了计算机科学、代数几何和表示理论的基础问题之间的深刻联系，本研究可能有助于将这些领域结合在一起，同时推进它们的基础问题。还将努力指导和培训几何复杂性理论方面的博士后研究人员，并通过期刊、会议和研讨会传播这一新兴领域的工作。本课题重点研究的P与NP猜想的代数变体是VP与VNP猜想，它表示永久值不能通过多项式大小和次数的代数电路来计算。由早期NSF基金CCF-1017760资助的项目揭示了代数几何和复杂性理论交界处的一个基本困难，称为几何复杂性理论鸿沟，需要通过任何现实的方法来克服这个猜想。这个鸿沟的存在是因为我们目前不知道复杂度类VP是否等于它的闭包。因此，在VP与VNP猜想的背景下，现在最紧迫的问题是要么证明VP等于它的闭包，要么在VP的闭包中构造不属于VP的特定候选族。本项目试图利用早期项目中开发的几何复杂性理论技术，结合代数几何的先进技术来研究这个问题。该项目还试图修改现有的几何复杂性理论方法来解决VP与VNP猜想，使用基于多重障碍的改进概念，以考虑到最近的负面结果。这些障碍物是代数几何和表征理论中的小工具，是永久物硬度的证明证书。该项目将通过一系列代数几何、表示理论和复杂性理论的中间问题来研究证明它们存在的问题。

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.