38
$\begingroup$

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.

$\endgroup$
  • 12
    $\begingroup$ Did you see Mulmuley's tutorial at FOCS (available at techtalks.tv/talks/1301 ) and have you read Ken Regan's exposition: theorie.informatik.uni-ulm.de/Personen/toran/beatcs/… ? 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. $\endgroup$ – Sasho Nikolov Jun 10 '11 at 16:18
  • 5
    $\begingroup$ 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." $\endgroup$ – Kaveh Jun 10 '11 at 22:54
  • 7
    $\begingroup$ I think GCT is aiming at VP vs. VNP and not P vs NP. $\endgroup$ – Iddo Tzameret Jun 11 '11 at 4:34
  • 6
    $\begingroup$ @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 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. $\endgroup$ – Joshua Grochow Jun 12 '11 at 0:59
  • 4
    $\begingroup$ @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... $\endgroup$ – Joshua Grochow Jun 12 '11 at 1:03
23
$\begingroup$

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

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

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

$\endgroup$
  • 1
    $\begingroup$ @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). $\endgroup$ – Joshua Grochow Jun 8 '18 at 19:40
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.