AF: Small: Geometric Complexity Theory Approach to the P vs NP problem

这个项目开发了一种几何方法来解决P与NP问题，称为几何复杂性理论。P与NP问题是数学科学的基本猜想，即定理证明不能自动进行。几何复杂性理论(GCT)是通过代数几何和表示论来解决这个问题和相关问题的一种方法。这种方法将复数领域上这些问题的变体归结为证明障碍的存在的问题，障碍是代数几何和表示论中的对象，在所讨论的下界问题中充当硬度证明。这些障碍的存在与代数几何和表示论中的某些正性假设密切相关。这个项目的目标是深入研究复杂性理论中的难度和数学中的实证性之间的联系，从而进一步扩展这一方法。由于科学和工程中易处理和难解决的问题之间的界限取决于P与NP问题，因此该方案中进行的研究对复杂性理论以及科学和工程的其他几个领域具有重要的智力意义。此外，由于GCT揭示了复杂性理论中的P与NP和相关问题以及纯数学中的基本正性问题之间的深刻联系，因此这一研究可能导致复杂性理论与几个分支数学之间的广泛合作，如代数几何和表示论。

This project develops a geometric approach to the P vs. NP problem, called geometric complexity theory.The P vs. NP problem is the foundational conjecture of mathematical sciences, which says that theorem proving cannot be automated. Geometric complexity theory (GCT) is an approach to this and related problems via algebraic geometry and representation theory. This approach reduces variants of these problems over the field of complex numbers to the problem of proving existence of obstructions, which are objects in algebraic geometry and representation theory that serve as proof certificates of hardness in the lower bound problems under consideration. The existence of these obstructions is deeply connected with certain positivity hypotheses in algebraic geometry and representation theory. The goal of this project is to study this connection between hardness in complexity theory and positivity in mathematics in depth and thereby extend the approach further.Since the boundary between the tractable and intractable problems in science and engineering depends on the P vs. NP problem, the study undertaken in this proposal is of central intellectual relevance to complexity theory as well as several other areas of science and engineering. Furthermore, since GCT reveals a deep connection between the P vs. NP and related problems in complexity theory and fundamental positivity problems in pure mathematics, this study could lead to extensive collaboration between complexity theory and several branches mathematics, such as algebraic geometry and representation theory.