AF: Small: Geometric Complexity Theory

几何复杂性理论是对计算机科学中最基本的杰出猜想P与NP的一种方法，这意味着定理证明不能自动进行。它目前的焦点是这个猜想的代数变体。这一方法是由PI在之前两笔NSF赠款支持的项目中发起的。它揭示了P对NP猜想的代数变体与代数几何和表示论的基本问题之间的深刻联系，这是与该项目最相关的两个数学领域。这个项目的目标是研究、加强和开发这些联系，以推动这一方法的进一步发展。数学和物理科学中易处理和难解决的问题之间的界限由P与NP问题来定义。因此，该项目中进行的研究对计算机科学以及数学和物理科学的其他几个领域具有重要的学术意义。由于几何复杂性理论揭示了计算机科学、代数几何和表示论的基本问题之间的深刻联系，本研究可能有助于将这些领域聚集在一起，同时在其基本问题上取得进展。本项目还将努力指导和培训几何复杂性理论的博士后研究人员，并通过期刊、会议和工作室传播这一新兴领域的工作。本项目关注的P与NP猜想的代数变体是VP与VNP猜想，即永久数不能通过多项式大小和次数的代数电路来计算。早些时候由美国国家科学基金会资助的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.