tag:blogger.com,1999:blog-3722233.post4232841350483328609..comments2023-03-25T10:00:22.914-05:00Comments on Computational Complexity: Two Recent Complexity Books omit Mahaney's theorem- ovesight or wisdom?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-89479551010740688752009-10-23T12:58:18.535-05:002009-10-23T12:58:18.535-05:00Hopefully I'm not putting words in his mouth, ...Hopefully I'm not putting words in his mouth, but when Lance said "who aren't primarily complexity researchers" maybe he meant "who aren't primarily *structrual* complexity researchers"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5833699974817882462009-10-18T10:04:12.668-05:002009-10-18T10:04:12.668-05:00Let me join in as the last person being referred t...Let me join in as the last person being referred to in the original post. I don't think there are "absolute" answers re this specific question or any other specific questions of this type.<br /><br />Each person, teaching or writing a book/survey etc, makes choices, which are governed by some principles. I think both my book and Arora-Barak book state clearly some of the principles that govern their choices, which I think is a good thing to do. So I'd refer you there.<br /><br />Lastly, let me protest at Lance comment by which the three authors are not "primarily complexity researchers"; I find this cmment very weird, to say the least...<br /><br />Oded GoldreichUnknownhttps://www.blogger.com/profile/14949903633532114035noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25540718350018442122009-10-06T20:39:36.927-05:002009-10-06T20:39:36.927-05:00Somebody pointed me to this discussion (as I am on...Somebody pointed me to this discussion (as I am one of the authors of the complexity books cited). I must point out that in my years of asking people what should or should not be covered in our book, I noticed that there was definitely a generational effect in people's answers. To give a random example, people of my generation (those introduced to complexity around 1990) find Toda's theorem a central result of complexity. People even 4-5 years younger than me often don't. (I dont intend to start another pointless discussion about whether or not they are wrong.)<br /><br />Both Lance and Bill were introduced to complexity in the early 1980s, which will undoubtedly show up in their tastes.<br /><br />Unfortunately, in writing our book we were forced to disappoint large subcommunities in the field, by devoting very limited space to subareas such as structural complexity, proof complexity, algebraic complexity, real complexity, communication and decision tree complexity etc. All of these subareas have been covered in excellent books that are almost as thick as our book. <br /><br />BTW here is my answer to the question in this post: I do not teach Mahaney's theorem in class but may give it as a exercise with a suitable hint. I believe the same is true of complexity courses at MIT, Berkeley, etc. I think it is quite a reasonable decision to teach it, but inevitably this would mean subtracting something whose omission would feel odd too.Sanjeev Aroranoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38395199859652095502009-10-05T22:08:50.823-05:002009-10-05T22:08:50.823-05:00It's worth mentioning that Oded's book cov...It's worth mentioning that Oded's book covers Fortune's theorem, or some generalization. Exercise 3.12: Prove that if SAT is Karp-reducible to a subset S of polytime computable G, and G\S is sparse, then SAT has a polytime algorithm.<br /><br />He also proves the Berman-Hartmanis Isomorphism results in Exercise 2.31.<br /><br />To Boaz: Based my limited understanding of the literature, your book does use the Ogiwara-Watnabe proof of Mahaney's theorem.<br /><br />To Bill: Personally, I think that while Mahaney's theorem is interesting, some generalizations (which you are probably familiar with) are much more interesting. We can define an equivalence relation on sets, where we say two sets are equivalent if their symmetric difference is sparse. The Ogihara-Watanabe techniques show that this equivalence preserves structural complexity in following sense: If a set S is NP-Hard and sparsely close to a set in P, then P=NP. (Notice that Oded's book generalizes Fortune's theorem in the direction of the above result). One can go further in this direction, see the paper “Closeness of NP-Hard Sets to Other Complexity Classes” by Bin Fu and Hong-zhou Li. I like this generalization of Mahaney's theorem more than the original theorem itself because it says the sparse-ness issue is more pervasive than just with sparse sets. One might come away from Mahaney's theorem and think that the result was "only" limited to sparse sets. However, even this more general result might not make the cut for a basis course because its hard (for me) to relate this to other results.Michael Forbeshttp://www.mit.edu/~miforbes/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38961880193341559202009-10-05T21:07:59.082-05:002009-10-05T21:07:59.082-05:00I enjoyed learning about Mahaney's theorem whi...I enjoyed learning about Mahaney's theorem while taking your class. I remember nothing of the proof, but I clearly remember the theorem. I think it's important for 2 reasons. (i) It gives a deeper understanding of what NP-complete problems are. It gives an idea that being NP-complete is not only about being hard to solve, but also about being able to encode enough information in order to allow all other NP problems to be reduced to it. (ii) It is a somewhat simple example of a theorem of the form X -> P=NP where X is not solve a NP-hard problem in poly time.<br /><br />On Yao's MST algorithm, I think it's very important to show some algorithm with log log n somewhere in the complexity, so students don't freak out when they hear of any algorithm that deviates from the "standard" complexities. Personally, I prefer to teach how to switch from Boruvka to Prim to attain the log log n factor.<br /><br />I believe both these examples impress students because they somehow contradict the intuition. Impressing students and contradicting the intuition are good enough reasons to teach a topic.Guilhermehttps://www.blogger.com/profile/16356657960297015642noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28407406057380808312009-10-05T17:50:59.555-05:002009-10-05T17:50:59.555-05:00As Boris notes, Mahaney's theorem is in our bo...As Boris notes, Mahaney's theorem is in our book. (BTW does the hint in our book follow Ogihara-Watanabe? If so we should add credit in the second edition.) <br /><br />We're to blame for Bill not finding it, since our index is pretty bad - your best bet in finding stuff is to avoid the index and try the "search inside" function in amazon. <br /><br />I agree this is an important result: this theorem, together with Karp-Lipton is part of the basis for our intuition that despite the "unary halting" example, non-uniformity doesn't really add that much power to computation. <br /><br /><br />But I still think it's OK not to teach it in a course. That's not saying much: any one term grad complexity class will necessarily omit some very basic and fundamental results. One of the ways I try to make up for this is by including more results in guided homework exercises, and the book reflects this tendency.<br /><br /><br />--Boaz BarakBoaz Barakhttps://www.blogger.com/profile/17419093502695262318noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90514015564081279232009-10-05T12:15:44.034-05:002009-10-05T12:15:44.034-05:00Exercise 2.30. (Berman's Theorem 1978) A lang...Exercise 2.30. (Berman's Theorem 1978) A language is called unary if every string in it is of the form 1^i (the string of i ones) for some i > 0. Show that if there exists an NP-complete unary language then P = NP. (See Exercise 6.9 for a strengthening of this result.)<br /><br />Exercise 6.9 (Mahaney's Theorem [Mah80]) Show that if a sparse language is NP-complete, then P = NP. (This is a strengthening of Exercise 2.30 of Chapter 2.)Unknownhttps://www.blogger.com/profile/06229416831400925212noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18227037801045612452009-10-05T12:10:01.094-05:002009-10-05T12:10:01.094-05:00I bought Aurora-Barak's book and really liked ...I bought Aurora-Barak's book and really liked it. Since they have page limitations, they cannot do justice to every great theorem. There are lots of great theorems out there. For a fast growing field like TCS, "static" books cannot do full justice.<br /><br />My strong suggestion is to have a Wiki dedicated to TCS. Very much like the open problem garden. This will enable different people (especially the experts) to write outlines of great results. Somebody with money and infrastructure (Eg, Intractability Center) should host such a Wiki.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86870528398828223992009-10-05T11:55:31.361-05:002009-10-05T11:55:31.361-05:00Lance
1) AGREE that IF you do the theorem you sho...Lance<br /><br />1) AGREE that IF you do the theorem you should use<br />Ogiwara-Watnabe proof.<br /><br />2) QUESTION: Why is Mahaney's theorem important? <br /><br />3) Caveat to last question:<br />Important compared to what? There are so many things to teach so one has to decide what is worth presenting.<br /><br />4) Defering to people who have thought longer and harder about what should be in the course than I have seems reasonable to me. <br /><br />5) Having said all that, you have given me (and hopefully our readers) food for thought. In the past I did Mahaney<br />AND many generalizations of it<br />(btt, word-reducible sets). I will certainly cut that out, though I may<br />still do Mahaney's theorem itself.<br />(Defering to someone else who has thought long and hard on these issues and runs a complexity blog!)Bill Gasarchnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39779687653693068442009-10-05T11:02:00.636-05:002009-10-05T11:02:00.636-05:00You are simply wrong Bill. First, because Mahaney&...You are simply wrong Bill. First, because Mahaney's theorem is very important and one ought to prove it (with the easier Ogihara-Watanabe proof) in a graduate complexity course. But also because you defer your own judgement to three people who aren't primarily complexity researchers simply because they wrote a book and you didn't.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4056842298768933722009-10-05T11:00:41.557-05:002009-10-05T11:00:41.557-05:00An interesting point. One thing it makes me think...An interesting point. One thing it makes me think about is: as a field matures some theorems/facts probably do need to lose their citations/provenance (even though this is unfair to the creators) for the good of the field. Like how the Myhill-Nerode Theorem disappears from the index of the3rd edition of "Automata Theory, Languages and Computation." At some point a field matures enough that the idea in question becomes part of how you think about automata, and calling it out by name/history seems to distract from the exposition.John Mounthttp://www.win-vector.com/noreply@blogger.com