tag:blogger.com,1999:blog-3722233.post115884073582520202..comments2021-04-19T22:59:36.221-05:00Comments on Computational Complexity: Short TakesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger24125tag:blogger.com,1999:blog-3722233.post-1158977166731150502006-09-22T21:06:00.000-05:002006-09-22T21:06:00.000-05:00Maybe someone has Levin's original paper (in russi...Maybe someone has Levin's original paper (in russian) and can confirm whether he proves that the satisfiability of boolean formulae is NP-complete.Alexhttps://www.blogger.com/profile/10531171312916299127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158969969592087062006-09-22T19:06:00.000-05:002006-09-22T19:06:00.000-05:00Anonymous of Comment 21, your implication that it ...Anonymous of Comment 21, your implication that it is Steve Cook who is upset about the nomenclature is mischievous and unfair.<BR/><BR/>Fair 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158968572231394262006-09-22T18:42:00.000-05:002006-09-22T18:42:00.000-05:00I'm surprised there's no reference to parametric c...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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158965956505878502006-09-22T17:59:00.000-05:002006-09-22T17:59:00.000-05:00Amazing that we as a community are so obsessed by ...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).<BR/><BR/>If 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158964269050915012006-09-22T17:31:00.000-05:002006-09-22T17:31:00.000-05:00I sent the link to this discussion to Leonid Levin...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.)<BR/><BR/>Levin 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.")<BR/><BR/>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.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158959666695395232006-09-22T16:14:00.000-05:002006-09-22T16:14:00.000-05:00Thank you for all the comments. Regarding the cred...Thank you for all the comments. <BR/><BR/>Regarding 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)<BR/><BR/>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.<BR/><BR/>We'll be very happy to hear any comments/suggestions/pointers/etc.. - please send all such mail to <BR/>complexitybook@gmail.com<BR/><BR/>Boaz Barak<BR/><BR/>p.s. another book in preparation that people might be interested to look at is Oded Goldreich's complexity book:<BR/>http://www.wisdom.weizmann.ac.il/~oded/cc-book.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158957172827339152006-09-22T15:32:00.000-05:002006-09-22T15:32:00.000-05:00Unfortunately, what we call the Cook-Levin theorem...<I>Unfortunately, what we call the Cook-Levin theorem is in neither in Cook's paper nor in Levin's. </I><BR/><BR/>I think you are splitting hairs. Cook proves that { DNF-tautologies } is NP-complete and explicitly observes that this problem is equivalent to SAT:<BR/><BR/><I>[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.</I><BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158952079882503632006-09-22T14:07:00.000-05:002006-09-22T14:07:00.000-05:00I hesitate to joing such a passionate discussion, ...I 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.)<BR/><BR/> Unfortunately, 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! <BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158941054298974142006-09-22T11:04:00.000-05:002006-09-22T11:04:00.000-05:00I should probably chime in here, since Garey & Joh...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...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158908072032236962006-09-22T01:54:00.000-05:002006-09-22T01:54:00.000-05:00The attribution of the theorem depends somewhat on...The 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. <BR/><BR/>In the mid to late 1980's there was more of a realization of the level of developments in the Soviet Union. <BR/>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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>Unlike Janos, however, I don't see any reason to consider expanding this further. Cook and Levin did two important things: <BR/><BR/>(1) Identify P and NP and some important NP problems not likely to be in P.<BR/><BR/>(2) Develop notions of reduction and show that these problems are complete, i.e. as hard as any in the class.<BR/><BR/>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. <BR/><BR/>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.<BR/><BR/>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).<BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158903755377630772006-09-22T00:42:00.000-05:002006-09-22T00:42:00.000-05:00Well, its referred to as "Cook's Theorem" in Papad...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158900531440557502006-09-21T23:48:00.000-05:002006-09-21T23:48:00.000-05:00First, "Cook-Levin Theorem" is fairly standard: I ...<I>First, "Cook-Levin Theorem" is fairly standard: I have been using it for a decade in courses at Chicago.</I><BR/><BR/>The common form is Cook's Theorem. This can easily be verified.<BR/><BR/><I>We could argue endlessly about who "really" "invented" NP-completeness, and it would not be outrageous even to make a claim for Godel.</I><BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158898818893286812006-09-21T23:20:00.000-05:002006-09-21T23:20:00.000-05:00First, "Cook-Levin Theorem" is fairly standard: I ...First, "Cook-Levin Theorem" is fairly standard: I have been using it for a decade in courses at Chicago.<BR/><BR/>As for the "who had the idea first" controversy, I think that first one has to remember the state of scientific communication between East and West in the seventies. There was no Internet. International phone calls were expensive, cumbersome and slow: in the USSR phone directories were considered confidential information. <BR/><BR/>Letters to the USSR were often read by censors, and not all of them arrived. Soviet scientists were routinely barred from attending scientific meetings outside the USSR, and certainly prevented from leisure trips outside the USSR.<BR/><BR/>Copying equipment was VERY scarce in the Eastern bloc, and it was tightly controlled. As an example, in Rumania, typewriters had to be registered with the police. There certainly was no Xerox, and photocpies were rare and crappy. <BR/><BR/>Second, the motivation and the approach by which Cook and Levin arrived at the theorem were different. <BR/><BR/>Cook was interested in the complexity of automated theorem-proving, and studied the simplest such question, namely whether there are good algorithms for sentential tautologies. (Logic without quantifiers and operators). <BR/>Of course, the outcome was his proof that satisfiability is NP-complete (and a definition of NP-completeness.) While he was on a roll, he also proved that some other combinatorial problems were NP-complete. (Incidentally, while he defined "Cook reductions" he actually used "Karp reductions" for the combinatorial problems.)<BR/><BR/>Levin came from a totally different tradition. Russian scientists had a longstanding interest in proving the "necessity of perebor", perebor being exhaustive search, to solve certain combinatorial problems. The standard problem was Boolean circuit minimzation, and there was even a "proof" that it required exponential search. A good survey of this history and Levin's role in it is <BR/>Trakhtenbrot's paper in Annals of <BR/>History of Computing v.6 n.4 1984.<BR/>They even had (without the terminology) a proof of parts of the non-relativization result (Baker-Gill-Solvay) before PvsNP was formally defined.<BR/><BR/>We seem to agree that Kolmogorov urged Levin to write down his result. Given Kolmogorov's reputation, that is proof enough for me that this was an independent result.<BR/><BR/>Both Cook and Levin are great scientists and people. Each, in his own way, had a strong influence in Complexity Theory by introducing NP-completeness to the West and East respectively. We could argue endlessly about who "really" "invented" NP-completeness, and it would not be outrageous even to make a claim for Godel. As usual, there was progress, and one has to give credit somewhat arbitrarily. I believe that Cook-Levin is an appropriate name for the theorem.Janos Simonhttps://www.blogger.com/profile/15677985672817404601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158893317739666762006-09-21T21:48:00.000-05:002006-09-21T21:48:00.000-05:00I know of several talented computer scientists who...<I>I know of several talented computer scientists who, when refereeing a paper, they read the abstract alone.</I><BR/><BR/>This is an idiotic statement. Sorry, no one does this. If so, they are at best a terrible referee.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158887978441181072006-09-21T20:19:00.000-05:002006-09-21T20:19:00.000-05:00I don't understand why you insist on using the art...<I>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.</I><BR/><BR/>Have 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. <BR/><BR/>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.<BR/><BR/>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.<BR/><BR/><BR/>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. <BR/><BR/>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. <BR/><BR/>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. <BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158882867983466122006-09-21T18:54:00.000-05:002006-09-21T18:54:00.000-05:00He had not "been giving talks about if for years"....<I>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".</I><BR/><BR/>1973 - 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.<BR/><BR/>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.<BR/><BR/>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?<BR/><BR/><I>I suggest you avail yourself of the facts before making such statements.</I><BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158877450317237002006-09-21T17:24:00.000-05:002006-09-21T17:24:00.000-05:00he had been giving talks about it for years and it...<I>he had been giving talks about it for years and it was "known" in Russia at the time.</I><BR/><BR/>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". 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.<BR/><BR/><I>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.</I><BR/><BR/>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.<BR/><BR/><I>Your persistence in using analogies that imply otherwise makes me question your honesty on this issue.</I><BR/><BR/>I suggest you avail yourself of the facts before making such statements.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158871956518435312006-09-21T15:52:00.000-05:002006-09-21T15:52:00.000-05:00What would people say if, say, Yau had, upon heari...<I>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><BR/><BR/>Again, a bad analogy. Levin was <I>not</I> 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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158861134102711932006-09-21T12:52:00.000-05:002006-09-21T12:52:00.000-05:00In part he delayed publication because he thought ...<I> 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. </I><BR/><BR/>If you sit in a proof, you run the risk of others publishing your result ahead of you. <BR/><BR/>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. <BR/><BR/>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".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158859639922888832006-09-21T12:27:00.000-05:002006-09-21T12:27:00.000-05:00Cook published his paper in 1971 and Levin publish...<I>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><BR/><BR/>This is a completely different situation.<BR/><BR/>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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158858775525601262006-09-21T12:12:00.000-05:002006-09-21T12:12:00.000-05:00What about the Goldriech's book? DO we have any re...What about the Goldriech's book? DO we have any reviewers for his book?<BR/><BR/>I 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. <BR/><BR/>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.<BR/><BR/>SKUAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158858075711862432006-09-21T12:01:00.000-05:002006-09-21T12:01:00.000-05:00I've read portions of the book, when it was author...I've read portions of the book, when it was authored solely by S. Arora (few months ago).<BR/><BR/>From what I saw: the book is very good! <BR/><BR/>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.<BR/><BR/>Nevertheless, the book is perfect for graduate students in complexity theory, and also as reference for researches in the field.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158855946566404282006-09-21T11:25:00.000-05:002006-09-21T11:25:00.000-05:00The book uses the non-standard "Cook-Levin Theorem...The book uses the non-standard "Cook-Levin Theorem". The authors have to go through contortions to justify this non-standard usage. I quote: <I>Around 1971, Cook and Levin in independent papers gave examples of combinatorial<BR/>NP-complete problems whose definition seems to have nothing<BR/>to do with Turing machines.</I><BR/><BR/>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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158852149785977292006-09-21T10:22:00.000-05:002006-09-21T10:22:00.000-05:00The complexity book on the web is very sketchy in...The complexity book on the web is very sketchy in some places. Maybe an updated version would be better.Anonymousnoreply@blogger.com