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.
