Sanjeev Arora and Boaz are nearing completion of their complexity book and they need your help. Please send them comments big and small. They particularly need you readers who are not (yet) experts in complexity to gauge the readability of the text.
The Royal Society has placed all of their journals online with free access through December. Their archives go back to '65 (that's 1665) in case you want to read Ben Franklin's paper on electricity.
The complexity book on the web is very sketchy in some places. Maybe an updated version would be better.
ReplyDeleteThe book uses the non-standard "Cook-Levin Theorem". The authors have to go through contortions to justify this non-standard usage. I quote: Around 1971, Cook and Levin in independent papers gave examples of combinatorial
ReplyDeleteNP-complete problems whose definition seems to have nothing
to do with Turing machines.
Cook published his paper in 1971 and Levin published his in 1973. Rewriting history to make 1971 and 1973 be "around 1971" is the wrong way to do things (apropos of Yau trying to create undue attributions).
I've read portions of the book, when it was authored solely by S. Arora (few months ago).
ReplyDeleteFrom what I saw: the book is very good!
It seems that for a beginning student it would be, at least psychologically, hard to start from such a book; as it is about 500 pages, and includes advanced material.
Nevertheless, the book is perfect for graduate students in complexity theory, and also as reference for researches in the field.
What about the Goldriech's book? DO we have any reviewers for his book?
ReplyDeleteI don't know why Arora-Borak introduced a chapter on Quantum Computation where they seem to introduce a bit of Shor's algorithm. It seems totally out of place, although a mild introduction to BQP would have been good.
Somebody needs to write a book on Quantum Computation from a CS point of view. N&C, an excellent book seems to be outdated now.
SKU
Cook published his paper in 1971 and Levin published his in 1973. Rewriting history to make 1971 and 1973 be "around 1971" is the wrong way to do things (apropos of Yau trying to create undue attributions).
ReplyDeleteThis is a completely different situation.
1. The discoveries were legitimately independent, because of communication difficulties between east and west during the cold war. The Yau situation is about adding onto something that someone else wrote -- Levin did not add onto Cook's work, both were original.
2. Publication date isn't everything. Levin was already giving talks on his work for a couple years before it was formally published. In part he delayed publication because he thought certain problems (e.g. Linear Programming) ought to be NP-Complete but couldn't find a proof. Once again, as far as the Poincare conjecture there is no question about the dates of "discovery" vs. "publication" -- one person clearly came first, and the other added onto it, whereas with Cook and Levin it seems likely that both discoveries were more or less contemporaneous (even besides iron curtain issues), despite the different publication dates.
In part he delayed publication because he thought certain problems (e.g. Linear Programming) ought to be NP-Complete but couldn't find a proof.
ReplyDeleteIf you sit in a proof, you run the risk of others publishing your result ahead of you.
What would people say if, say, Yau had, upon hearing about Wiles proof, stepped forward and said: "I had a proof of Fermats's too but I was sitting on it because I wanted to solve the Taniyama-Shimura conjecture as well". I doubt people would be as sympathetic.
The field has standard practices for joint attribution of independent discoveries. There are two requirements (1) independent discovery and (2) publication in close proximity in time. Levin's fails in both counts: (1) he had ideas but did not write the article until after hearing of Cook's result and (2) publication was not nearly simultaneous, hence the contorted "around 1971".
What would people say if, say, Yau had, upon hearing about Wiles proof, stepped forward and said: "I had a proof of Fermats's too but I was sitting on it because I wanted to solve the Taniyama-Shimura conjecture as well".
ReplyDeleteAgain, a bad analogy. Levin was not sitting on the proof, as I said, he had been giving talks about it for years and it was "known" in Russia at the time. If in the situation you describe, Yau had started giving talks about his proof, but then Wiles had actually published first, it would be completely legitimate for Yau to want joint credit. Levin's result was public (or as public as it could be given the political climate), and this is not invalidated because its journal appearance was later than Cook's.
Your analogy again falsely implies that Levin (or anyone in Russia) somehow had access to Cook's result, and was publishing in response to it. This is not accurate. The results, and their publication, were completely independent. Your persistence in using analogies that imply otherwise makes me question your honesty on this issue.
he had been giving talks about it for years and it was "known" in Russia at the time.
ReplyDeleteHe had not "been giving talks about if for years". By Levin's own words he discovered it in 1971, so he couldn't have done so "for years". Yes he he had been working in the subject for a while (and giving talks on it) but that is not the same as having the result.
Your analogy again falsely implies that Levin (or anyone in Russia) somehow had access to Cook's result, and was publishing in response to it. This is not accurate.
To the contrary, Kolmogorov got wind of the publication of Cook's result and encouraged Levin to write up the results Levin had been outlining in his seminars. How do I know? The story has been related in print by Levin and Kolmogorov.
Your persistence in using analogies that imply otherwise makes me question your honesty on this issue.
I suggest you avail yourself of the facts before making such statements.
He had not "been giving talks about if for years". By Levin's own words he discovered it in 1971, so he couldn't have done so "for years".
ReplyDelete1973 - 1971 is "years." I wasn't trying to claim that he had been giving talks for years before Cook published -- my whole point was that the discoveries were fairly close in time, not that Levin was far in advance.
You are correct about Kolmogorov hearing about Cook's result -- I had forgotten that, and was mistaken in saying the publication was completely independent. But it's still very different from the situation you outlined: you were talking about a result that was kept private until another publication. Levin's result had been public for some time, and even when it was published the knowledge of Cook's result was just word-of-mouth about a related result in the US -- unless I'm very mistaken, Levin still had no access to Cook's manuscript.
I don't understand why you insist on using the artificial "journal publication" date to decide this issue, rather than public presentation of the result. To use your own example, very few people would date Perelman's proof by its appearance in a peer-reviewed journal -- why insist on that here, when the communication gap was far greater than it is anywhere today?
I suggest you avail yourself of the facts before making such statements.
You corrected one fact on which I was mistaken, but that doesn't affect my point at all: if your claim is so evident, you shouldn't need to use such deceptive metaphors to argue it.
I don't understand why you insist on using the artificial "journal publication" date to decide this issue, rather than public presentation of the result.
ReplyDeleteHave you ever attended a talk from the Russian school of mathematics? A famous Russian mathematician described the typical talk as 50 minutes about general philosophy of mathematics followed by ten minutes of broad strokes hinting of a result. [Several well known Russian mathematicians have heartily agreed in person with this description]. Was Levin talk one of those? I don't know for sure, but given the time it took for him to put the results in writable form (paper was submitted later in 1972), it seems his proof idea was rather sketchy.
Keep in mind that these "routine" reductions were state of the art and unchartered territory back then. Karp's reductions appeared a full year later to great and well deserved acclaim. That's how hard the "details" were back then.
In terms of the taint, Levin's write-up took place while he already had the advantage of having independent confirmation of the result. I know of several talented computer scientists who, when refereeing a paper, they read the abstract alone. Usually this is enough for them to reconstruct the result and if they can't then the result is almost invariably wrong. Yes, these are top notched computer scientists, but so is Leo, so we cannot dismiss this advantage in the final write up.
Lastly, so you can see there is no hidden agenda or ill motives, I'd like to add that when I first heard of the independent discovery of Levin I thought nothing of it as simultaneous discovery is common: as editor I've managed mergers of indepentdenlty discovered results. Later, when I learned it was from the Kolmogorov school I wasn't at all surprised, as I've always been a fan of Andrei Nikolaevich's life work as a researcher and as a teacher.
Only later, while tending to my math history buff proclivities, did I learn in piecemeal fashion the details of the discovery as related in interviews, biographies, and personal chats. What at first seemed an independent discovery started to look more and more as simply Levin being scooped by Cook's work.
This shouldn't be a shocker. I doubt there is an active computer scientist who hasn't had a half cooked result (no pun intended) scooped at least once. In these cases if one cannot point to a finished or nearly finished write up, one just eats it up: it comes with the territory. It seems to me that in this case the facts point out that this is what happened.
Lastly, Levin has always acted in the most honest manner, explaining openly what happened, accurately describing the timeline of events, and being subdued in his precedence claims. In this context the "around 1971 ... in independent papers" statement is terribly misleading and a disservice to Leo.
I know of several talented computer scientists who, when refereeing a paper, they read the abstract alone.
ReplyDeleteThis is an idiotic statement. Sorry, no one does this. If so, they are at best a terrible referee.
First, "Cook-Levin Theorem" is fairly standard: I have been using it for a decade in courses at Chicago.
ReplyDeleteThe common form is Cook's Theorem. This can easily be verified.
We could argue endlessly about who "really" "invented" NP-completeness, and it would not be outrageous even to make a claim for Godel.
Oh it would be. Godel asked the P=NP question or something close to it, but he was far from the concept of NP-completeness.
Well, its referred to as "Cook's Theorem" in Papadimitriou, but as "The Cook-Levin Theorem" in Sipser. Since I would wager many more students are introduced to NP-completeness through Sipser, I claim that "The Cook-Levin Theorem" is the 'standard' name.
ReplyDeleteThe attribution of the theorem depends somewhat on the age of the source. In the 1970's in the West it was exclusively referred to as Cook's Theorem. There were few exchanges in the 1970's and typically two year delays in translating papers from Russian; I can imagine it was similar or worse in the other direction.
ReplyDeleteIn the mid to late 1980's there was more of a realization of the level of developments in the Soviet Union.
We heard the story of Peter Gacs and a fellow Czech grad student returning from some mid 1970's summers Moscow and the U.S., respectively, with news of the wonderful ideas of the new theories of NP-completeness and perebor which turned out to be the same thing.
Sipser's book, which has been the most widely used textbook in the field for a decade, uses the Cook-Levin attribution. This does not diminish anyone's contribution.
There were some differences in approach between the two: Cook used satisfiability as the progenitor problem; Levin used tiling, though they both apply the same tableau idea. In most texts today, the approach of Cook and Karp is followed, though Lewis and Papaditrimiou's text does begin with tiling as Levin does.
Unlike Janos, however, I don't see any reason to consider expanding this further. Cook and Levin did two important things:
(1) Identify P and NP and some important NP problems not likely to be in P.
(2) Develop notions of reduction and show that these problems are complete, i.e. as hard as any in the class.
The Cook-Levin Theorem itself is about (2). Both Godel's letter to von Neumann and Edmonds' "Paths, Trees, and Flowers" paper go a long way, if not all the way, towards (1). Neither remotely touches on (2) so it would be absurd to credit them with any part of the Cook-Levin Theorem.
Both Godel and Edmonds identified P with the notion of a good algorithm and they both identified what we now know of as NP characterizations. Godel goes on to explicitly discuss satisfiability and conjecture that P is different from NP. Edmonds is a little less explicit about candidate hard problems, and a little less explicit about the NP definition, though decision versions of generic optimization problems (ILP) are clearly his natural candidates.
From the historical point of view, though, Godel's letter had no influence because it was unpublished; its main value is not as part of building mathematics/computational complexity but rather as evidence that one of the great thinkers of the age thought that the P versus NP question was important and understood its implications. It seems that one should only credit work that had influence on later work (or should have if those later authors had paid attention).
On the other hand, Edmonds' paper clearly did have direct influence in complexity (as well as algorithm design), particularly on the identification of P and Karp's work on NP.
I should probably chime in here, since Garey & Johnson was one of those early books that used "Cook's Theorem" even though we knew of Levin's work and mention it in Section 5.1 of that book. What we called "Cook's Theorem" is the proof that SAT is NP-complete. This particular result is not in Levin's 1973 paper. Among the six problems he lists, he includes the problem of determining whether a predicate calculus statement is a tautology. This, however, is a more general problem than SAT, and in any case no proof is included in the paper. Thus on purely technical grounds "SAT is NP-complete" cannot be attributed to Levin's paper, and so it would seem inappropriate to call this the "Cook-Levin" Theorem as Arora and Borak currently do. Leonid definitely deserves credit for independently coming up with the concept of NP-completeness, but there should be a more accurate way of honoring him. At least that was our thinking back in 1978...
ReplyDeleteI hesitate to joing such a passionate discussion, especially about events that happened before I entered kindergarten. Boaz and I did look at the original papers. I am guessing we were ultimately swayed by Sipser's convention (which he presumably arrived at after his research into his survey of the P vs NP problem, where he discusses the Perebor/Kolmogorov school.)
ReplyDeleteUnfortunately, what we call the Cook-Levin theorem is in neither in Cook's paper nor in Levin's. Thus another valid position --which nobody seemed to take here---could be to call it just Karp's Theorem!
The fairest thing seems to be that we should add in our historical notes (or in a long footnote immediately below the theorem) a summary of the above discussion.
Unfortunately, what we call the Cook-Levin theorem is in neither in Cook's paper nor in Levin's.
ReplyDeleteI think you are splitting hairs. Cook proves that { DNF-tautologies } is NP-complete and explicitly observes that this problem is equivalent to SAT:
[The Davis-Putnam] procedure was designed to determine whether a given formula in CNF is satisfiable, but of course the "dual" procedure determines whether a given formula in DNF is a tautology.
It would have been pompous to followup with a theorem stating SAT is NP-complete. The paragraph above, together with the DNF proof takes care of that.
Thank you for all the comments.
ReplyDeleteRegarding the credit for NP completeness in general and of 3SAT in particular, Sanjeev and I will definitely research this some more, and make sure when revising this chapter and its historical notes section that we represent the history as accurately as possible. (BTW the historical notes sections in all the chapters are still in very rough shape - we are working on them but we'd be grateful for any pointers)
I do believe a chapter on quantum computation belongs in such a book - I gave two lectures on that topic in my graduate complexity class, and I know others did as well.
We'll be very happy to hear any comments/suggestions/pointers/etc.. - please send all such mail to
complexitybook@gmail.com
Boaz Barak
p.s. another book in preparation that people might be interested to look at is Oded Goldreich's complexity book:
http://www.wisdom.weizmann.ac.il/~oded/cc-book.html
I sent the link to this discussion to Leonid Levin and he categorically denies that he or Kolmogorov knew of Cook's paper before Levin wrote his. He is not sure where "Anonymous" got his story. (Anonymous is welcome to write to me privately if he/she so wishes.)
ReplyDeleteLevin also mentioned that David Johnson's understanding of his article is based upon a mistranslation. Trakhtenbrot published a better translation in 1984 (which of course was too late for the G+J book). One of his NP-complete languages was satisfiability of boolean formulae. (He called it "propositional calculus.")
One other issue that wasn't mentioned thus far was the definition of "reduction" used in the papers. (All three papers --Cook's, Karp's and Levin's---used a different notion of reduction. Levin's notion includes a polynomial-time transformation of the witnesses.)
Amazing that we as a community are so obsessed by who gets credit for what. I understand why someone would be upset for not being credited for something they did; I don't understand someone being upset for being credited along with someone else for results arrived at independently (regardless of the exact chronological order).
ReplyDeleteIf Arora and Barak are forced to go to these lengths for every citation in their book, we can be assured to see their book published by 2010.
I'm surprised there's no reference to parametric complexity in the text. Isn't this an important approach to understanding the relative complexity of different NP-complete problems?
ReplyDeleteAnonymous of Comment 21, your implication that it is Steve Cook who is upset about the nomenclature is mischievous and unfair.
ReplyDeleteFair attribution of credit is an important component of participation in a research community. It prevents research getting politicized, this is why so many people are revelling in Yau's discomfiture.
Maybe someone has Levin's original paper (in russian) and can confirm whether he proves that the satisfiability of boolean formulae is NP-complete.
ReplyDelete