tag:blogger.com,1999:blog-3722233.post111427621894109259..comments2019-10-14T12:11:35.608-04:00Comments on Computational Complexity: Favorite Theorems: NP-CompletenessLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-1114735956389926572005-04-28T20:52:00.000-04:002005-04-28T20:52:00.000-04:00I'd find it interesting, at least, to see what oth...<I>I'd find it interesting, at least, to see what other fixtures of today's landscape had trouble becoming accepted. </I><BR/><BR/>Daniel Simon's paper "On the power of quantum computation" was initially rejected from STOC. But its manuscript inspired Peter Shor to generalize its ideas so as to solve the discrete log problem in quantum polynomial time (and then factoring as well). In the subsequent FOCS, both of their papers were accepted. I think that Simon's result a fixture in the quantum computing landscape.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114610559583948732005-04-27T10:02:00.000-04:002005-04-27T10:02:00.000-04:00I heard that GMR was initially rejected because it...I heard that GMR was initially rejected because it wasn't clearly written. The ideas in the paper weren't rejected--they weren't initially understood at least partially because of the exposition.<BR/> <BR/>Rejecting a badly written paper with a great idea is not an instance of people not accepting something because it is ahead of its time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114563179415532562005-04-26T20:52:00.000-04:002005-04-26T20:52:00.000-04:00We have the GMR paper as an example of something t...We have the GMR paper as an example of something that was so far ahead of its time that it was initially rejected. Are there other examples that people have in mind? I'd find it interesting, at least, to see what other fixtures of today's landscape had trouble becoming accepted. <BR/><BR/>-David MolnarAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114487283314873532005-04-25T23:48:00.000-04:002005-04-25T23:48:00.000-04:00All this fixation with credit is quite meaningless...All this fixation with credit is quite meaningless. We are all progressing slowly and building on each other works, and it is impossible to tell the contribution of a particular work or line of research before enough time has passed. Actually, as is evidenced by the comments above on the works of Cook&Levin, even with time it is not possible to completely isolate the contribution of one paper.<BR/><BR/>Credit is necessary mechanism but it is not the most important thing. In fact, if a contribution is truly revolutionary then it is quite likely not to be appreciated at first - some of the field's best papers, including the GMR paper that invented interactive proofs and zero knowledge were initially rejected from our conferences.<BR/><BR/>Thus, what is important is not whether Reingold's work is better than Trifonov or vice versa (which, despite the awards decision, we don't really know at the moment) but that we know much more about probabilistic low-space computation today than we did a year ago.<BR/><BR/>--BoazAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114481126340252392005-04-25T22:05:00.000-04:002005-04-25T22:05:00.000-04:00In an interview, Levin commented that he was advis...In an interview, Levin commented that he was advised by Kolmogorov to rush to publication his results on NP-completeness. Apparently Andrei Nikolaevich had heard rumors of the publication of similar results in the west by Cook.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114457186367486242005-04-25T15:26:00.000-04:002005-04-25T15:26:00.000-04:00Man, why are Computer Scientists so result-centric...Man, why are Computer Scientists so result-centric? Our goal as a field is not to get tight bounds for everything we can get our hands on; it is to understand fully the nature of computation,<BR/>and the related mathematics.<BR/><BR/>Tight bounds are an indication of progress, but not means unto themselves. Thus if Trifonov's result had been as insightful as Reingold's, the extra O(log log n) factor would be merely an annoyance, not evidence that Reingold should receive most of the credit.<BR/><BR/>The fact is that Reingold's proof is revolutionary--unlike the previous works achieving progressively exponents 3/2, 4/3, ..., the essence of Omer's idea can be explained in a sentence or two, and for people who have given thought to the problem previously, that sentence is enough to reproduce the proof from scratch.<BR/><BR/>See also Dinur's recent (and, again, revolutionary) proof of the PCP theorem which is "inspired," in part by Omer's technique.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114450435020940782005-04-25T13:33:00.000-04:002005-04-25T13:33:00.000-04:00Congrats to both Trifonov and Reingold for their b...<B>Congrats</B> to both Trifonov and Reingold for their best paper awards at STOC!!! Well deserved winners.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114447154541793022005-04-25T12:39:00.000-04:002005-04-25T12:39:00.000-04:00> One reason why credit hasn't> been divided equal...> One reason why credit hasn't<BR/>> been divided equally between<BR/>> Reingold and Trifonov is that<BR/>> Reingold's proof is so much more<BR/>> elegant and insightful. Such a<BR/>> criterion may seem rather<BR/>> arbitrary, but I'm sure most<BR/>> theorists are in agreement on<BR/>> this point, it's not as<BR/>> subjective as one may think. In<BR/>> any case time's the final judge... <BR/><BR/>I don't believe in that. Trifonov result is weaker and therefore Reingold's result will receive main credits; otherwise Trifonov's result deserves the same amount of credit.<BR/>Still, Trifonov has been awarded best student paper in STOC'05 (Reingold result was awarded best paper of the conference).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114443618273171362005-04-25T11:40:00.000-04:002005-04-25T11:40:00.000-04:00By awarding equal credit to results proved "indepe...By awarding equal credit to results proved "independently" (i.e., without knowledge of an existing result), aren't we providing a kind of incentive for researchers to _not_ fully investigate previous work? (Yes, you could make the case that in the Cook/Levin case knowledge of the previous result would have been very difficult to obtain, but now...)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114388855049331202005-04-24T20:27:00.000-04:002005-04-24T20:27:00.000-04:00One reason why credit hasn't been divided equally ...One reason why credit hasn't been divided equally between Reingold and Trifonov is that Reingold's proof is so much more elegant and insightful. Such a criterion may seem rather arbitrary, but I'm sure most theorists are in agreement on this point, it's not as subjective as one may think. In any case time's the final judge...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114379229334310082005-04-24T17:47:00.000-04:002005-04-24T17:47:00.000-04:00It is interesting to note that parts of the NP-com...It is interesting to note that parts of the NP-completeness concept were known before the two papers.<BR/><BR/>In a letter to von Neuman, Godel poses the question of the complexity of proofs of tautologies of sentential calculus (does a Boolean formula always evaluate to "TRUE"?) as a very important problem of Mathematics. This is, of course the question "NP=coNP?", closely related to the P vs NP problem.<BR/><BR/>Unrelated to the above, researchers in Operation Research have tried to understand Integer Programming: some subcases reduce to Linear Programming (which we now know is in P, and even then researchers knew that in practice was "easy" because of the usually efficient simplex method). In contrast, some subcases seemed to be as hard as the general problem. These hardness results were effectively reductions between NP-complete problems.<BR/><BR/>Finally, the idea of encoding computations into logical formulae was well known in Computability Theory.<BR/><BR/>Of course none of this diminishes the beauty, importance, or impact of the papers by Cook and Levin. It just might help give some of the scientific sources that (at least in retrospect) contributed to this great result.Janos Simonhttps://www.blogger.com/profile/15677985672817404601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114369067604804622005-04-24T14:57:00.000-04:002005-04-24T14:57:00.000-04:00I think that Lance's original post suggesting that...I think that Lance's original post suggesting that there should be any question about acceptance of Trifonov's work was ridiculous. These were essentially simultaneous results. Yes, one was stronger but both were major results and submitted to the same conference. It just happened that word got out a bit faster for the stronger result.<BR/><BR/>The issue with NP-completeness is a relativistic notion of simultaneity. <BR/>It is clear that, in the West, Cook's paper and Karp's follow-on paper had already been widely disseminated before Levin's work was even published (and Levin's work was not known in the West until several years later). <BR/><BR/>However, there is a well-known story that from the point of view of an observer in Czechoslovakia (actually two observers meeting after simultaneous East-ward and West-ward trips) the two events appeared to be simultaneous.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114365718396627432005-04-24T14:01:00.000-04:002005-04-24T14:01:00.000-04:00The student in question (Vladmir Trifonov), and th...The student in question (Vladmir Trifonov), and the researcher in question (Omer Reingold) have both been awarded best paper for their results at STOC 2005.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114321452897065892005-04-24T01:44:00.000-04:002005-04-24T01:44:00.000-04:00The student independently discovered a weaker re...The student independently discovered a <I> weaker </I> result, otherwise of course he deserves the same amount of credit.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114319674278782292005-04-24T01:14:00.000-04:002005-04-24T01:14:00.000-04:00Wasn't it just a few weeks ago that this blog talk...Wasn't it just a few weeks ago that this blog talked about a student who independently discovered a result a mere few weeks after some researchers and it was questioned whether he deserved any credit at all?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114312931668565432005-04-23T23:22:00.000-04:002005-04-23T23:22:00.000-04:00> Why is then Levin given equal credit if he was t...> Why is then Levin given equal credit if he was two years late?<BR/><BR/>Your point was taken into consideration by the ACM: Cook got the Turing award, while, unfortunately, Levin did not.<BR/><BR/>Levin's discovery was independent of Cook's discovery. I think it is only fair that both of them should be credited equally for their discovery.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1114307282019352212005-04-23T21:48:00.000-04:002005-04-23T21:48:00.000-04:00From your message it seems Cook published his pape...From your message it seems Cook published his paper in 1971 and Levin in 1973. Why is then Levin given equal credit if he was two years late? Usually academic credit is given on a first-past-the-post basis.Anonymousnoreply@blogger.com