Monday, January 22, 2007

Complexity Textbooks

A reader asks
What are currently considered to be the best textbooks for complexity? I know the choice is small (Papadimitriou is probably still the best even if it is very outdated and somewhat buggy), do most of the lecturers just write their own lecture notes? Is there a set of notes that is especially popular and also used by others. I also know the upcoming book by Arora/Barak but it's still far from complete, would you recommend it for teaching?
You have more choices than you think with textbooks by Homer and Selman, Hemaspaandra and Ogihara, Ko and Du, Wegener, and several others. Also several complexity theorists have put their lecture notes on line, quite a valuable resource. Jin-Yi Cai has the makings of a textbook from his lecture notes.

The topics and style of a computational complexity course varies from instructor to instructor and no single book would work for all. You really just need to find what best works for you and your class.

I personally don't use a textbook when I teach graduate complexity. I've been so close to the field no book would fit my philosophy unless I write it myself. And that's not going to happen anytime soon.


  1. There is an excellent book that is in preparation, but in a very mature stage, by Oded Goldreich. It can be found here:

  2. Dexter Kozen's new book on Theory
    of Computation (in a lecture like
    format similar to his book on
    algorithms) has a nice collection of

  3. Can you get rich by writing a book?

  4. Yes, of course. It might be hard though to get rich with a book on complexity theory.

  5. Conspicuous by it's absence
    is ofcourse, Sipser's book.


    I used an earlier version of the Arora-Barak book for a course several years ago and I was very happy with it. (The course began with the polynomial-time hierarchy and students had already seen NP-completeness and basic space complexity.) It had a great selection of topics - though not all I wanted to cover, well thought out presentations that did not merely mimic the original papers, and far fewer bugs than more than just one of the published texts listed.

  7. Why are you not going to write your own textbook anytime soon ?
    Are you too busy writing papers ?
    (and blogging!)

  8. It is a shame that no good complexity text exists (I don't consider the Papadimitriou one very good, and anyway it is now outdated), I am glad to see that Goldreich and Barak/Arora are addressing the issue. You can also check out Goldreich's online lecture notes (which are less complete but possibly easier to read than his book if you already know the material).

    Lance, I am curious why you would not use any other book for your course. Is what you teach really that different from, say, what is in Gooldreich's book?

  9. I am also very happy with what I've read of Arora/Barak.

    Related question--who (online or in print) has got the best problem sets and/or puzzles about or germane to complexity theory?

    It would be nice if paper authors occasionally had the humility to say in the abstract, e.g., 'Theorems 4 and 5 could be proved by an undergrad', just to point people to opportunities to develop their chops. Wishful thinking, though...

  10. Yes; the selection of complexity texts has improved a lot in the past few years.

    Regarding the ones mentioned that I've looked at much:

    Du and Ko is quite fine. My primary complaints, having spent a fair bit of time with it are exercise errata and proof readability. The proofs tended to be not so much terse as much as just having too much internal coupling. I needed to keep track of around twice as many details as necessary to follow the typical proof, requiring a half dozen rereads until I really understood what was going on.

    Still a perfectly decent book! I only say a lot about it because the course I took used it. I've since given it a thorough but not quite complete readthrough. It's probably a step up from your typical graduate text. Be particularly wary of definitions contained in exercises, because that's where a lot of the exercise errata lie.

    Hemaspaandra and Ogihara is targeted at a slightly higher level; I don't believe it's intended for a first course in complexity.

    Someone mentioned Sipser, which is the other way around. It's targeted at an intro-to-theory course that would be a prereq for a course on complexity. Second edition is really nice, but I hear that first edition has excessive errata.

    I don't know that much about the rest, as of yet.

  11. Laci Lovasz's lecture notes from a complexity course 10 years ago are also online.

    Seemed fine when it was used for a course I took, but haven't compared it to other texts on the subject.

  12. Here at the University of Minnesota, the grad level computational complexity course taught every few years by the excellent Professor Sturtivant, who lectured almost entirely from memory (including proofs!), we used Sipser and Du and Ko together, mostly for the homeworks. Since I am "just an undergrad" I found Sipser much easier to read, but Du and Ko had a more material. My biggest complaint was that the notations between those two books, the discrete math book, and the algorithms book were all slightly different, which made cross referencing annoying. I don't think that any of the books had legends for the notation, either, preferring that you figure out their conventions from the contexts.

    Unfortunately I seem to have taken all of the theoretical computer science classes here at the U, so there's nothing left for grad school.