This work is licensed under a
Creative Commons License.
|
Friday, August 30, 2002
Posted by Lance
Great Books: Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson.Despite that 23 years have passed since its publication, I consider Garey and Johnson the single most important book on my office bookshelf. Every computer scientist should have this book on their shelves as well. NP-completeness is the single most important to come out of theoretical computer science and no book covers it as well as Garey and Johnson.
The popularity of the book comes mainly from its appendix that consumes nearly half the pages. This section gives a comprehensive list of NP-complete problems in a well-structured and organized fashion. If one needs to determine whether a problem X is NP-complete, one can almost always either find X in the appendix or find a Y in the appendix that easily reduces to X. And the name-instance-question format has inspired many imitators, for example P-completeness and NP optimization.
It would be a mistake to ignore the first half of the book. Garey and Johnson has the best introduction to computational complexity I have ever seen. It gives basic proofs of NP-completeness results but more importantly gives the tools one needs to generate new NP-complete proofs. Section 6 discusses issues about what to do if one has to write an algorithm for an NP-complete problem. Section 7 discusses many different advanced concepts in complexity that give a taste to the richness of the area. And don't miss the terminological history in Section 5.2.
Of course Garey and Johnson misses the last 23 years of research. Many more NP-complete problems are known. Linear Programming and Composite Number are listed as open questions. The results on hardness of approximation based on probabilistically checkable proofs came long after the publication of the book. Section 7, "Beyond NP-completeness" is woefully out of date. Nevertheless no book before or since has captured the critical NP-completeness concept better than this classic book.
7:54 AM #
Wednesday, August 28, 2002
Complexity Class of the Week: S2P
Posted by Lance
CCW IntroSuppose a polynomial-time computable judge has to decide whether a string is in a language. Two lawyers submit written arguments to convince the judge, one arguing for the string in the language and the other arguing for the string to be out of the language. Neither lawyer can see the others arguments. For what languages can we have the judge always convinced?
Russell and Sundaram define the class S2P to capture this notion. Formally a language L is in S2P if there is a polynomial-time predicate A and a polynomial q such that
where |y| and |z| are bounded by q(|x|).
- If x is in L then there is a y such that for all z, A(x,y,z).
- If x is not in L then there is a z such that for all y, not A(x,y,z).
Personally I like to think of S2P as for every input x defining an exponential binary matrix A where the (i,j) entry of A is computable in polynomial time from i,j and x. If x is in the language then A has a row of all ones. If x is not in the language then A has a column of all zeros.
NP∪coNP is in S2P is in Σ2P∩Π2P. Russell and Sundaram show that S2P is closed under Turing reduction and relativizations to BPP. This implies BPP, MA and PNP are contained in S2P.
A big breakthrough for S2P comes from Cai who shows that S2P is contained in ZPPNP. His proof is builds on the learning algorithm of Bshouty, et. al. Sengupta noticed that a variation of the Karp-Lipton result shows that if NP has polynomial-size circuits then the polynomial-time hierarchy collapses to S2P. This also improves Kannan's result to show that for any fixed k, there is a language in S2P that does not have nk-size circuits. S2P is the smallest class known to have these properties.
S2P has come up recently in several of my research projects. Beigel, Buhrman, Fejer, Fortnow, Longpre, Stephan and Torenvliet show that a language L is in S2P if and only if there is a function f mapping Σ* to {1,2,3} such that L is polynomial-time Turing reducible to all 2-enumerators for f. Buhrman and Fortnow give an oracle separating ZPPNP from Σ2P∩Π2P which by Cai's result gives the first relativized world separating S2P from Σ2P∩Π2P. Fortnow, Pavan and Sengupta show that if PNP[2] = PNP[1] then the polynomial-time hierarchy collapses to S2P improving on earlier collapses. You will have to trust me on the latter two results as they are in the process of being written up.
Whether S2P contains ZPPNP is open even for relativized worlds. Since AM∩coAM is in ZPPNP, one could try to prove that AM∩coAM is in S2P or a specific language in AM∩coAM such as graph isomorphism.
There are variations on the class S2P and I recommend reading the papers of Russell and Sundaram and Cai for these and other results about this interesting class.
2:07 PM #
Tuesday, August 27, 2002
Posted by Lance
Complexity Class of the WeekWhen I was at U. Chicago, we would have a semiregular feature call the Complexity Class of the Week where we would pick a complexity class or other concept and on a white board in the lounge write the definition, what was known, how it related to other classes and perhaps most importantly what open questions remained.
I decided to revive this tradition here on this virtual whiteboard in the ultimate lounge known as the internet.
Scott Aaronson has set up a Complexity Zoo that gives a short description of many classes that make a good reference. We will go more in depth for a single class or concept but Aaronson's site makes for a good reference for other classes we mention.
Watch this space tomorrow for the first complexity class of the week. Feel free to email me with suggestion for future classes of the week, especially if you are willing to contribute a write-up.
4:13 PM #
Saturday, August 24, 2002
Posted by Lance
Last spring, I saw Copenhagen, a great play about the 1941 meeting between physicists Niels Bohr and Werner Heisenberg. The play has a wonderful scene, describing a trip Bohr made to Paris to learn about some new theory. At various cities along his route, local physicists would meet Bohr at the train station to pick his brains about this new theory on the way down and again on Bohr's return trip.Fast foward to the summer of 1987. Neil Immerman shows that nondeterminstic space is closed under complement. He sends the paper to Mike Sipser at MIT, where I was a grad student at the time. Mike was in Russia and we didn't find out about the result at MIT until we got an email talk announcement about it at Berkeley. It wasn't for several months that we found out the same result was proven at about the same time by Slovakian undergrad R�bert Szelepcs�nyi.
Much ado was made about how fast the results on interactive proof systems and probabilistically checkable proofs were distributed during 1990-92. Hardly anyone raises an eyebrow on how fast the primality results spread despite that they came from a "third-world country". Manindra Agrawal sends out an email on Sunday, August 4. By Monday the results are verfied, discussed and at least one seminar presented the result. By Thursday there was an article in the New York Times. Now three weeks later, the primality result seems like old news. Sure Manindra and his students had this nice algorithm for primality but what have they done lately?
During the week of August 4 I was on vacation and missed all of the fun. When I retured mixed in with about 50 emails on primality, were 2 emails annoucing the death of Edsger Dijkstra. Dijkstra hasn't been an active member of the theory community for a long time and I don't believe I ever met him. However, his polynomial-time algorithm for shortest path will have more practical applications than the polynomial-time algorithm for primality ever will.
6:30 AM #
Friday, August 23, 2002
Posted by Lance
This has been an exciting summer for computational complexity.Food for thought from Joe Kilian: Primality, until now, has always been the key example of a problem that we knew how to solve quickly with a probabilistic algorithm but not without using randomness. If the new primality algorithm had been discovered in the 70's would randomized complexity still have developed as well as it did?
- Complexity Theorist Manindra Agrawal and his students Nitin Saxena and Neeraj Kayal have given the first provably efficient algorithm for primality. This is a breakthrough result, exciting not only as an answer to a long-standing and important problem, but also in the beauty and simplicity of the solution.
- The computational complexity conference held in Montreal broke all records with a 140 participants. I can't wait for next year's conference in Aarhus, Denmark. Check out the new website for the conference, computationalcomplexity.org.
- Kudos to Madhu Sudan, winner of the Nevanlinna Prize for his work on probabilistically checkable proofs and error-correcting codes. This prize is given with the Fields medal every four years for work in "information science". Congrats Madhu!
8:03 PM #
Thursday, August 22, 2002
Posted by Lance
This is my complexity web log. I'll be giving random thoughts about computational complexity and about mathematics and computer science in general.7:31 PM #
Archives
