This work is licensed under a
Creative Commons License.
|
Monday, April 21, 2008
Ketan Mulmuley Responds
Posted by Lance
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.
6:38 AM #
-
Lance's post generated lot of comments and I am somewhat surprised that there are no responses to this post so far!
-
Anonymous #1:
Because nobody wants to argue with the Ketan himself, which is a bit sad.
-
> Because nobody wants to argue with the
> Ketan himself, which is a bit sad.
Not at all, it's just that you need to wait for the required month.
-
It's because Ketan's post is grounded, as opposed to Lance's sensationalist fare. I guess that's why Lance is a good blogger. He knows how to stir up a crowd.
-
I found Ketan's response very reasonable. I fail to see why a complexity theory expert would not want to spend a bit of time to try to understand a new and very different approach to complexity theory.
-
Ketan:
What do you mean precisely when you say "the P vs. NP problem in characteristic zero"? Are you referring to Blum-Shub-Smale model of computation over Z (as opposed to Z/2Z)?
Assuming that "the P vs. NP problem in characteristic zero" is not the same as the ordinary P vs. NP problem (presumably this would be characteristic 2?), does your work have any implications for the ordinary P vs. NP problem? I don't think you've made this very clear.
But if "the P vs. NP problem in characteristic zero" is actually meant to be synonymous with the ordinary P vs. NP problem, then please say so.
-
To Anon 6: I think Ketan works with Valiant's algebraic version of P versus NP rather than with Blum, Shub and Smale's.
-
I fail to see why a complexity theory expert would not want to spend a bit of time to try to understand a new and very different approach to complexity theory.
As far as I can tell, there has not been a publication using this approach in over 7 years. There has also not been a paper on this topic that was not co-authored by Mulmuley. (Please correct me if I am wrong.) It is therefore hard to tell whether anyone except Mulmuley believes this approach to be viable. I'm not saying it is not, just that if I were evaluating whether to spend 1 month reading a paper, I would at least like to know that there are other people I trust who have found the paper worthwhile.
I also took a brief look at the "flip" paper and did not find it very well written. Again, I am not placing fault on Mulmuley but just explaining why people aren't rushing to read the paper or try this approach.
-
Kevin,
the P vs. NP in char zero is different from its BSS or valiant form. it is
explained in detail in GCT1. basically one
takes an appropriate (co)-NP-complete integral function E(X) and the problem is
to show that it does not have an arithmetic circuit of poly size over Z.
This is a formal implication of
the usual P vs. NP conjecture (or rather
the nonuniform version which says E(X)
considered over F_2
does not have poly-size boolean circuits) and hence has to be proved first
anyway. that is why GCT focuses on
that first. actually the first problem
to consider is valiant's determinant vs.
permanent problem in char zero, which is
used as a running example in GCTflip to
illustrate the basic ideas.
it is conjectured that the flip paradigm
would also work in the context of the
usual P vs. NP problem over F_2 or F_p.
This would be discussed in detail in
GCT11. But implemention of the flip over
a finite field would be much harder
than in char zero. hence the focus on
the latter.
regards,
ketan
-
I also took a brief look at the "flip" paper and did not find it very well written. Again, I am not placing fault on Mulmuley but just explaining why people aren't rushing to read the paper or try this approach.
Note that people said (and still say) the much the same thing about Perelman's papers on the Poincare conjecture. It's a sad state of affairs when community needs to be told to value content over form.
-
Note that people said (and still say) the much the same thing about Perelman's papers on the Poincare conjecture.
But Perlman's paper solves a long-standing open problem. The GCT stuff only claims to be an approach to solving a long-standing open problem. Also, the (apparent) intended purpose of the GCT paper mentioned in this post is to introduce people to the topic, whereas Perlman's paper was directed at experts.
It's a sad state of affairs when community needs to be told to value content over form.
If I was convinced the content was worthwhile, I would put up with the bad form. The point of Anon 8 was that it is not clear the approach is worthwhile.
-
Anonymous 8:
When one tries to cover basics in algebraic geometry, rep theory and use plethora of technicalities not used by our community on a regular basis in 103 pages, people are bound to say that the paper is not well written. On the other hand, if it were "well-written", it would have turned in to a 200 page paper, which again would have troubled people (because of the length). I would recommend reading the GCT-Abstract, available on Ketan's homepage. Now it is easy going and might give you a reason to proceed with this paper. Moreover, Ketan suggested devoting 1 month to the paper, which I guess is enough to get a basic understanding of the paper. Besides if Ketan markets his work, then people might take interest in it.
-
Yes, as anon 12 pointed out GCTabstract
available on the personal Chicago web page should be read
before GCTflip. Also available on the
web page is GCTintro, which is a monograph
consisting of lecture notes for an introductory course on GCT for computer
science graduate students in Chicago. It
covers a small part of GCTflip, which
however gives a glimpse of the basic idea of GCT, in a leisurely self-contained way. The graduate students here feel that
it is easier to read than GCTflip, which
has to cover much more ground in short space. GCTflip had to be terse
because of the page-limit constraints,
as anon 12 correctly guessed.
The monograph GCTintro has to be polished before its publication
(by Cambridge University Press). please let me know whatever
comments you may have so as to make
this monograph as easy to read as
possible for the TCS community. One has
to accept the responsibility of communicating the basic idea of GCT to the community as simply as possible. But it is hoped that the community would also understand the
huge challenge in this task given a
mismatch between the language of GCT (algebraic geometry, representation
theory, quantum groups, so forth) and
the traditional language of
the TCS community. It is a trying time,
but we can
overcome the difficulties together. please let me know (by email)
whatever difficulties you encounter
in reading GCTabstract, GCTintro, and GCTflip (in that order) and i will
do my best.
regards,
ketan
-
WRT anon8, as is evident from the post, someone other than KM (KVS from CMI) gave a series of talks on the subject.
Also Regan wrote an expository article, so others are reading it. Its just that people not well-versed with algebraic geometry are not inclined to admit it or improve upon it.
Links to this post:
Weblog Home
Archives
