7
$\begingroup$

I'm very interested in Computer Science (computational complexity, etc.). I've already finished a University course in the subject (using Sipser's "Introduction to the Theory of Computation").

I know the basics, i.e. Turing Machines, Computability (Halting problem and related reductions), Complexity classes (time and space, P/NP, L/NL, a little about BPP).

Now, I'm looking for a good book to learn about some more advanced concepts. Any ideas?

  • 2
    I think this would be more appropriate at Stack Overflow, no?2010-07-21
  • 2
    What is your definition of CS? The post looks like you are referring to theory of computation.2010-07-21
  • 2
    @Ben - Good question. It's sort of the reason I asked this. Computer Science is a mathematical field, as such it belongs here. There is some overlap, but for serious analysis of computational complexity, I don't think Stack Overflow is the right place (most people there are programmer, not mathematicians).2010-07-21
  • 0
    @Mgccl - Yes, I'm referring to theory of computation / computational complexity. But that entire branch of mathematics is called "Computer Science" (confusing it with "Computer Science" as used to mean "a degree in programming"). [edit - ok this cross posting has got to stop! Cross posted Mgccl, then Katie! :)]2010-07-21
  • 6
    can I ask why this was closed? Besides a possible need to change "Computer Science" to "Theoretical Computer Science" or somesuch in the title, and maybe remove "Best," this seems an appropriate question related to learning mathematics.2010-07-21
  • 0
    I'm voting to reopen, because I think questions about books should be appropriate. Even MO does not typically close them. It should be community wiki, though.2010-07-21
  • 0
    @Akhil - I think the problem wasn't that it was about a book, it was the Computer Science aspect of it. Agree about the cw, my bad.2010-07-21
  • 1
    @Edan: Theoretical computer science is essentially mathematics, and MO has accepted it on its website -- note that there are people like Scott Aaronson and Peter Shor active there. I don't see why we should kick out lower level tcs questions.2010-07-21
  • 0
    @Akhil - I *don't* think we should kick it out, I think we should include it. By the way, I knew Scott Aaronson was active in MO, didn't know Peter Shor was there as well.2010-07-22
  • 0
    I did a little digging and from what I can find, most of the books on computational theory appear to be introductory books that cover all of the topics you mentioned (automata, regular expressions, regular languages, context-free languages, undecidability, complexity). The more advanced books appear to be exclusively on a specific topic. Can you specify what topics you are interested in - that might help with book suggestions.2010-07-23
  • 0
    This question could be more appropriate here: http://cstheory.stackexchange.com/2010-12-04
  • 0
    @Akhil: I can think of all sorts of advanced computational complexity texts, but I'm at a loss to think of a modern advanced text on automata (concepts touched on via the Chomsky hierarchy).2011-05-09

6 Answers 6

9

The Art of Computer Programming

(Donald Knuth)

The legendary book (of multiple volumes, still incomplete) can't go without mention. For learning about algorithms and their complexities, there is no rival. It's written with practicality in mind, though from a largely theoretical perspective.

The Art of Computer Programming

  • 0
    I've never read it, but I always got the feeling it was much more of a practical book on using algorithms for programming, much less of an actual TCS book (e.g., does it talk about complexity classes?).2010-07-22
  • 2
    That's partially but not fully true. There's some good discussion of complexity classes in relation to the algorithms given, from what I know.2010-07-22
  • 1
    As great as these volumes are, they don't address the mathematics that the OP is looking for. TAOCP covers lots of great mathematics as -tools- for analyzing situations that CS (including TCS) might encounter, but it does not come close to covering the main subjects of TCS (complexity theory, automata and recursion theory, programming language semantics. As broad and deep as Knuth's knowledge is, these volumes do not discuss the TCS topics alluded to by the OP. (Knuth did organize a consensual naming of ..well...the name of "NP-completeness", but that's the extent of the contribution)2011-05-09
5

Papadimitriou's Computational Complexity covers complexity theory at a higher level than Sipser, but has essentially no prerequisites.

5

You may enjoy "Computers and Intractability: A Guide to the Theory of NP-Completeness" by Garey and Johnson. It is widely considered a classic in the field and it takes the subject matter of the last chapters of Sipser into the stratosphere.

Also... why not just follow the bibliograpy in Sipser?

3

Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak, is a more up to date advanced 'introduction' text.

1

I think you should determine what kinds of applications you want to apply CS to and then learn general theory relevant to those applications. Not all theory is equally applicable everywhere.

  • 5
    It is usually preferable to post such remarks as comments.2010-07-23
-1

The Mythical Man-Month more for software engineering but absolutely one of the best books ever written about programing IMO.