Collins Conference Room
Working Group
  US Mountain Time

Our campus is closed to the public for this event.

Abstract.  P versus NP is the question of whether brute-force search algorithms can always be simulated by significantly more efficient algorithms. Given that thousands of computational problems in science, business, mathematics, medicine, engineering, and throughout society are in NP, the P versus NP problem is perhaps the most important problem in all of mathematics and compute science. Even if it turns out that the answer is “no” (as most researchers expect), a proof of this fact is expected to shed a bright light on our understanding of computing and the universe.

Geometric Complexity Theory (GCT) is a program aimed at showing P is not equal to NP, using deep mathematical techniques from algebraic geometry and representation theory. This working group brings together experts in GCT with experts in adjacent fields – such as commutative algebra and classical computational complexity – who have not worked on GCT before. The goal of the working group is to push forward the limits of our current understanding of the geometric nature of computational complexity.

Research Collaboration
SFI Host: 
Josh Grochow, J. M. Landsberg, and Jerzy Weyman

More SFI Events