Mulmuley's GCT program

Question

It is sometimes claimed that Ketan Mulmuley's Geometric Complexity Theory is the only plausible program for settling the open questions of complexity theory like P vs. NP question. There has been several positive commentaries from famous complexity theorists about the program. According to Mulmuley it will take a long time to achieve the desired results. Entering the area is not easy for general complexity theorists and needs considerable efforts to get a handle on algebraic geometry and representation theory.

1. Why is GCT considered to be capable of settling P vs. NP? What is the value of the claim if it is expected to take more than 100 years to reach there? What are its advantages to other current approaches and those that may rise in the next 100 years?

2. What is the current state of the program?

3. What is the next target of the program?

4. Has there been any fundamental criticism of the program?

I would prefer answers that are understandable by a general complexity theorist with the minimum background from algebraic geometry and representation theory assumed.

Answer 1

As pointed out by many others, much has already been said on many of these questions by Mulmuley, Regan, and others. I will offer here just a brief summary of what I think are some key points that haven't yet been mentioned in the comments.

1. As to why GCT is considered plausibly capable of showing $P \neq NP$ many answers have already been given elsewhere and in the comments above, though I think no one has yet mentioned that it appears to avoid the known barriers (relativization, algebrization, natural proofs). As to its value - I think even if it takes us 100 years, we will learn something new about complexity along the way by studying it from this angle.

2. • Some progress is being made on understanding the algebraic varieties, the representations, and the algorithmic questions that arise in GCT. The principal researchers I know of who have done work on this are (in no particular order): P. Burgisser, C. Ikenmeyer, M. Christandl, J. M. Landsberg, K. V. Subrahmanyan, J. Blasiak, L. Manivel, N. Ressayre, J. Weyman, V. Popov, N. Kayal, S. Kumar, and of course K. Mulmuley and M. Sohoni.

   • More concretely, Burgisser and Ikenmeyer just presented (STOC 2011) some modest lower bounds on matrix multiplication using the GCT approach ($n^2 + 2$, compared to the currently best known $\frac{3}{2}n^2 +O(n)$). Although these lower bounds are not new bounds, they at least give some proof-of-concept, in that the representation-theoretic objects hypothesized to exist in GCT do exist for these modest lower bounds on this model problem.

   • N. Kayal has a couple papers on the algorithmic question of testing when one polynomial is in the orbit of another or is a projection of another. He shows that in general these problems are NP-hard but that for special functions like permanent, determinant, and elementary symmetric polynomials, these problems are decidable in P. This is a step towards some of Mulmuley's conjectures (that certain harder problems - deciding orbit closure - are in P for special functions such as determinant).

3. I don't have much more specific to say on this than the answer to 2.

4. As far as I know there has not been fundamental criticism, in the sense that I have not seen any criticism which really discredits the program in any way. There has certainly been discussion about why such techniques should be necessary, the value of the program given the long time horizons expected, etc., but I would characterize these more as healthy discussion than fundamental criticism.

Answer 2

I think this article by Ketan D. Mulmuley will answer at least question #1 (possibly 2) On P vs. NP and Geometric Complexity Theory