[Computational Complexity] Ketan Mulmuley Responds
- Someone pointed out to me your post where it is stated that, according to me, any approach to separate P from NP must go through GCT. This is not what I think or said. One cannot really say that GCT is the only way to separate P from NP or that any approach must go through it. Indeed as the article (On GCT, P vs. NP and the Flip I: A High Level View)—henceforth referred to as GCTflip—which describes the basic plan of GCT, clearly states: GCT is a plausible approach to the P vs. NP problem. But as it also explains there are good mathematical reasons to believe why it may well be among the "easiest" approaches to the P vs. NP problem.
One such argument—the zero information loss argument—was presented by K.V. in his talk. According to it, any approach to separate the permanent from the determinant in characteristic zero must understand, in one way or the other, the fundamental century-old problem in representation theory, called the Kronecker problem, or rather its decision form. (though this understanding may be expressed in that approach in a completely different language). This is what I repeated during the lunch after that talk, and this is perhaps what the post is referring to.
The only known special case of this problem which is completely solved is the Littlewood-Richardson problem. The most transparent proof of this (which also provides far deeper information regarding this problem needed in GCT, unlike other proofs) goes through the theory quantum groups, and the only known good criterion for the decision version requires the saturation theorem for Littlewood-Richardson coefficients. GCT strives to lift this most transparent proof to the Kronecker problem, and more generally to the generalized subgroup restriction problem (and its decision form), which is needed in the context of the P vs. NP problem in characteristic zero.
All this is explained in detail in the article GCTflip mentioned above. It does not assume any background in algebraic geometry or representation theory. It has been read by the computer science graduate students here. They had no problem reading it. But it does need a month. It is my hope that you would spare a month sometime for the sake of the P vs. NP problem.
Posted By Lance to Computational Complexity at 4/21/2008 06:38:00 AM