39

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.

Anonymous
  • 4,041
  • 19
  • 43
  • 12
    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 Jun 10 '11 at 16:18
  • 1
    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 Jun 10 '11 at 22:22
  • As for your first question, It is believed that GCT can overcome known barriers for settling the P vs NP problem. – Mohammad Al-Turkistany Jun 10 '11 at 22:26
  • @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 – Kaveh Jun 10 '11 at 22:41
  • 5
    Related blog posts: 1, 2. Also Scott 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 Jun 10 '11 at 22:54
  • 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? – Sasho Nikolov Jun 10 '11 at 23:00
  • 2
    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 Jun 10 '11 at 23:44
  • 7
    I think GCT is aiming at VP vs. VNP and not P vs NP. – Iddo Tzameret Jun 11 '11 at 04:34
  • 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. – Joshua Grochow Jun 12 '11 at 00:59
  • 4
    @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 Jun 12 '11 at 01:03
  • see also How difficult is it to use the Mulmuley-Sohoni approach(GCT) to show KNOWN complexity separations? and How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)? – vzn Sep 26 '12 at 19:22
  • @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 Apr 08 '17 at 22:18
  • 1
    @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 Apr 09 '17 at 04:09
  • @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 May 06 '17 at 04:43
  • @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 May 06 '17 at 05:36
  • @JoshuaGrochow could this possibly be the essential reason that GCT has not been working so far? – Turbo May 06 '17 at 10:00
  • @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 May 06 '17 at 10:29

2 Answers2

23

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.

    • 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.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • 1
    @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 Jun 08 '18 at 19:40
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

Joshua Herman
  • 1,661
  • 17
  • 38