<p>I think this article by  Ketan D. Mulmuley will answer at least question #1  (possibly 2) <a href="http://ramakrishnadas.cs.uchicago.edu/gctexplicit.pdf">On P vs. NP and Geometric Complexity Theory</a></p>

CC BY-SA 3.0
2011-06-11T20:39:19.263Z
2011-06-11T20:39:19.263Z
Joshua Herman
<p>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.</p>

<ol>
<li><p>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.</p></li>
<li><ul>
<li><p>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.</p></li>
<li><p>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. </p></li>
<li><p>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 <em>closure</em> - are in P for special functions such as determinant). </p></li>
</ul></li>
<li><p>I don't have much more specific to say on this than the answer to 2.</p></li>
<li><p>As far as I know there has not been <em>fundamental</em> 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.</p></li>
</ol>

CC BY-SA 4.0
2018-06-08T19:40:15.127Z
@user124864: In principle yes. GCT is just an approach to showing lower bounds, whatever those lower bounds might be. It seems like it should work better for functions characterized by their symmetries, but the latter property doesn't depend on the numerical value of the lower bound you want to show (e.g. quasipoly vs exp).
Joshua Grochow
CC BY-SA 3.0
2011-06-12T01:01:00.193Z
2011-06-12T01:01:00.193Z
Joshua Grochow
<p>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.</p>

<ol>
<li><p>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?</p></li>
<li><p>What is the current state of the program?</p></li>
<li><p>What is the next target of the program?</p></li>
<li><p>Has there been any fundamental criticism of the program?</p></li>
</ol>

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

CC BY-SA 3.0
2011-06-10T16:18:31.343Z
Did you see Mulmuley's tutorial at FOCS (available at http://techtalks.tv/talks/1301/ ) and have you read Ken Regan's exposition: http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column78.pdf ? Mulmuley definitely gave his intuition for why he thinks his program is viable (and I think he argues that it's even to some extent necessary), and also why it's difficult.
Sasho Nikolov
CC BY-SA 3.0
2011-06-10T22:22:04.443Z
Personally, I believe GCT wont resolve the P vs NP problem. The solution would be completely unexpected and would require entirely novel ideas.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-06-10T22:26:55.457Z
As for your first question, It is believed that GCT can overcome known barriers for settling the P vs NP problem.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-06-10T22:41:00.480Z
@Sasho, based on the last sentence of the question, it seems to me that the OP is asking for an explanation from a different perspective. @OP, also check [GCT workshop](http://intractability.princeton.edu/blog/2009/12/geometric-complexity-theory-workshop/)
Kaveh
CC BY-SA 3.0
2011-06-10T22:54:45.750Z
Related blog posts: [1](http://blog.computationalcomplexity.org/2008/04/how-to-prove-np-different-from-p.html), [2](http://blog.computationalcomplexity.org/2008/04/ketan-mulmuley-responds.html). Also [Scott](http://www.scottaaronson.com/blog/?p=458) writes: "Mulmuley’s GCT program is the only approach to P vs. NP I’ve seen that even has serious aspirations to “know about” lots of nontrivial techniques for solving problems in P (at the least, matching and linear programming).  For me, that’s probably the single strongest argument in GCT’s favor."
Kaveh
CC BY-SA 3.0
2011-06-10T23:00:26.883Z
@Kaveh: I suspect OP might know about my links, but I thought it's worth posting them anyways. But I don't quite understand what you mean: the tutorial and Regan's writeup both are aimed at a complexity theory audience with minimum/no background from algebraic geometry, no?
Sasho Nikolov
CC BY-SA 3.0
2011-06-10T23:44:38.703Z
This question makes me wary and crochety. I am not a complexity theorist, but it appears the FOCS video, tutorial and JACM draft on Mulmuley's page directly address  the technical part of questions 1 to 4. He even addresses criticism regarding proving easier lower bounds first.  The "what is the value of" type question can be asked in any context and to me, is terribly vague and shortsighted.
Vijay D
CC BY-SA 3.0
2011-06-11T04:34:05.857Z
I think GCT is aiming at VP vs. VNP and not P vs NP.
Iddo Tzameret
CC BY-SA 3.0
2011-06-12T00:59:56.653Z
@Iddo: Actually it can be aimed at many things (more than it is currently aimed at). For "perm v det over $\mathbb{C}$" it is aimed at $\overline{VP_{ws}}$ vs $VNP$ (see http://arxiv.org/abs/0907.2850). However, over finite fields and for functions other than perm and det, it can be aimed directly at P vs NP.
Joshua Grochow
CC BY-SA 3.0
2011-06-12T01:03:31.983Z
@Mohammad: Just because a solution would be unexpected and require entirely novel ideas doesn't mean that that's not how the solution will go. Indeed, many already believe that resolving P vs NP by *any method* will require entirely novel ideas...
Joshua Grochow
CC BY-SA 3.0
2012-09-26T19:22:29.803Z
see also [How difficult is it to use the Mulmuley-Sohoni approach(GCT) to show KNOWN complexity separations?](http://cstheory.stackexchange.com/questions/948/how-difficult-is-it-to-use-the-mulmuley-sohoni-approachgct-to-show-known-compl) and [How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?](http://cstheory.stackexchange.com/questions/170/how-does-the-mulmuley-sohoni-geometric-approach-to-producing-lower-bounds-avoid)
vzn
CC BY-SA 3.0
2017-04-08T22:18:01.730Z
@JoshuaGrochow 'However, over finite fields and for functions other than perm and det, it can be aimed directly at P vs NP' how can we do this? Also can GCT be useful in non-separation statements like P=BPP?
Turbo
CC BY-SA 3.0
2017-04-09T04:09:21.860Z
@Turbo: (1) "How can we do this" - long story. Short version is to start from highly symmetric functions that capture P and NP; see the function E(X) constructed in GCT I. (2) It depends what you mean by "GCT". If you mean the specific suggestion of finding multiplicity obstructions, then it seems unlikely that it could be used to prove non-separation statements in general. However, for P=BPP we know from hard v rand that this follows from a different separation statement. On the other hand, for a more direct geometric approach to derandomization, see GCT V.
Joshua Grochow
CC BY-SA 3.0
2017-05-06T04:43:25.167Z
@JoshuaGrochow sorry to get picky on this. Supposing if $P \neq BPP$ is the truth is there a way to apply GCT to see the truth?
Turbo
CC BY-SA 3.0
2017-05-06T05:36:35.680Z
@Turbo: Separating P from BPP, if $P \neq BPP$ is true, is actually a bit tricky, because the lower bound techniques in GCT are non-uniform (so, e.g., they actually would show $NP \not\subseteq P/poly$ rather than just $NP \neq P$). But $BPP \subseteq P/poly$, so you can't separate P from BPP by a nonuniform lower bound. So you'd need some way to combine uniformity with the techniques of GCT. Allender's perm lower bound comes to mind, but that's a far cry from really combining uniform arguments with GCT...
Joshua Grochow
CC BY-SA 3.0
2017-05-06T10:00:19.527Z
@JoshuaGrochow could this possibly be the essential reason that GCT has not been working so far?
Turbo
CC BY-SA 3.0
2017-05-06T10:29:38.257Z
@JoshuaGrochow may be we should try $NEXP\not\subseteq P/poly$ http://blog.computationalcomplexity.org/2003/02/nexp-not-in-ppoly.html with GCT if this is possible?
Turbo
<cc.complexity-theory><big-picture><algebraic-complexity><p-vs-np><gct>
Mulmuley's GCT program
Anonymous
# Mulmuley's GCT program

(Asked by: username_0 on 2011-06-10)

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.

**Tags:** cc.complexity-theory, big-picture, algebraic-complexity, p-vs-np, gct
> **Comments:**
> **username_1**: Did you see Mulmuley's tutorial at FOCS (available at http://techtalks.tv/talks/1301/ ) and have you read Ken Regan's exposition: http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column78.pdf ? Mulmuley definitely gave his intuition for why he thinks his program is viable (and I think he argues that it's even to some extent necessary), and also why it's difficult.  
> **username_2**: Personally, I believe GCT wont resolve the P vs NP problem. The solution would be completely unexpected and would require entirely novel ideas.  
> **username_2**: As for your first question, It is believed that GCT can overcome known barriers for settling the P vs NP problem.  
> **username_3**: @Sasho, based on the last sentence of the question, it seems to me that the OP is asking for an explanation from a different perspective. @OP, also check [GCT workshop](http://intractability.princeton.edu/blog/2009/12/geometric-complexity-theory-workshop/)  
> **username_3**: Related blog posts: [1](http://blog.computationalcomplexity.org/2008/04/how-to-prove-np-different-from-p.html), [2](http://blog.computationalcomplexity.org/2008/04/ketan-mulmuley-responds.html). Also [Scott](http://www.scottaaronson.com/blog/?p=458) writes: "Mulmuley’s GCT program is the only approach to P vs. NP I’ve seen that even has serious aspirations to “know about” lots of nontrivial techniques for solving problems in P (at the least, matching and linear programming).  For me, that’s probably the single strongest argument in GCT’s favor."  
> **username_1**: @Kaveh: I suspect OP might know about my links, but I thought it's worth posting them anyways. But I don't quite understand what you mean: the tutorial and Regan's writeup both are aimed at a complexity theory audience with minimum/no background from algebraic geometry, no?  
> **username_4**: This question makes me wary and crochety. I am not a complexity theorist, but it appears the FOCS video, tutorial and JACM draft on Mulmuley's page directly address  the technical part of questions 1 to 4. He even addresses criticism regarding proving easier lower bounds first.  The "what is the value of" type question can be asked in any context and to me, is terribly vague and shortsighted.  
> **username_5**: I think GCT is aiming at VP vs. VNP and not P vs NP.  
> **username_6**: @Iddo: Actually it can be aimed at many things (more than it is currently aimed at). For "perm v det over $\mathbb{C}$" it is aimed at $\overline{VP_{ws}}$ vs $VNP$ (see http://arxiv.org/abs/0907.2850). However, over finite fields and for functions other than perm and det, it can be aimed directly at P vs NP.  
> **username_6**: @Mohammad: Just because a solution would be unexpected and require entirely novel ideas doesn't mean that that's not how the solution will go. Indeed, many already believe that resolving P vs NP by *any method* will require entirely novel ideas...  
> **username_7**: see also [How difficult is it to use the Mulmuley-Sohoni approach(GCT) to show KNOWN complexity separations?](http://cstheory.stackexchange.com/questions/948/how-difficult-is-it-to-use-the-mulmuley-sohoni-approachgct-to-show-known-compl) and [How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?](http://cstheory.stackexchange.com/questions/170/how-does-the-mulmuley-sohoni-geometric-approach-to-producing-lower-bounds-avoid)  
> **username_8**: @JoshuaGrochow 'However, over finite fields and for functions other than perm and det, it can be aimed directly at P vs NP' how can we do this? Also can GCT be useful in non-separation statements like P=BPP?  
> **username_6**: @Turbo: (1) "How can we do this" - long story. Short version is to start from highly symmetric functions that capture P and NP; see the function E(X) constructed in GCT I. (2) It depends what you mean by "GCT". If you mean the specific suggestion of finding multiplicity obstructions, then it seems unlikely that it could be used to prove non-separation statements in general. However, for P=BPP we know from hard v rand that this follows from a different separation statement. On the other hand, for a more direct geometric approach to derandomization, see GCT V.  
> **username_8**: @JoshuaGrochow sorry to get picky on this. Supposing if $P \neq BPP$ is the truth is there a way to apply GCT to see the truth?  
> **username_6**: @Turbo: Separating P from BPP, if $P \neq BPP$ is true, is actually a bit tricky, because the lower bound techniques in GCT are non-uniform (so, e.g., they actually would show $NP \not\subseteq P/poly$ rather than just $NP \neq P$). But $BPP \subseteq P/poly$, so you can't separate P from BPP by a nonuniform lower bound. So you'd need some way to combine uniformity with the techniques of GCT. Allender's perm lower bound comes to mind, but that's a far cry from really combining uniform arguments with GCT...  
> **username_8**: @JoshuaGrochow could this possibly be the essential reason that GCT has not been working so far?  
> **username_8**: @JoshuaGrochow may be we should try $NEXP\not\subseteq P/poly$ http://blog.computationalcomplexity.org/2003/02/nexp-not-in-ppoly.html with GCT if this is possible?  

---

## 2 answers

### Answer by username_6 on 2011-06-12. Score: 23 | Accepted answer

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.

> **Comments:**
> **username_6**: @user124864: In principle yes. GCT is just an approach to showing lower bounds, whatever those lower bounds might be. It seems like it should work better for functions characterized by their symmetries, but the latter property doesn't depend on the numerical value of the lower bound you want to show (e.g. quasipoly vs exp).  

---

### Answer by username_9 on 2011-06-11. Score: 5

I think this article by Ketan D. Mulmuley will answer at least question #1 (possibly 2) [On P vs. NP and Geometric Complexity Theory](http://ramakrishnadas.cs.uchicago.edu/gctexplicit.pdf)


---

