Is there a definitive book on computational complexity?

I would recommend Computational Complexity - A Conceptual Perspective by Oded Goldreich.

If you want a book: Introduction to the Theory of Computation by Sipser.

When in doubt, Wikipedia is often a great starting point following the references as your needs dictate. Added in response to comment: Where "follow the references" may mean a trip to a university library or bookstore. I've not read Sipser 2006, but expect that recommendation is good and it is in the Wikipedia bibliography.

Not every resource is on the web (yet), dead trees still have a nice information density.

I did went through wikipedia and also google searches. However I am looking for a book that cover the subject more in depth. And I mean university course in depths – paan Apr 16 '11 at 13:15 Thanks!

That's one of the very best Wikipedia articles I've read. – Pete Wilson Apr 16 '11 at 13:33 @paan -- If you look at the references in the article that @msw mentioned, you'll find eight textbooks and four surveys. – Pete Wilson Apr 16 '11 at 13:35.

I'd recommend Computational Complexity: A Modern Approach. It describes both recent achievements and classical results of computational complexity theory.

The undergraduate course I did recommended Papadimitriou - Computational Complexity; it's been a while since I looked at it, but as it's still the recommended book, I take that as reasonable commendation.

How about Knuth's series The Art of Computer Programming, that is a real classic.

Not really about complexity theory. – Adrian Petrescu May 1 '11 at 22:07 I think you've misunderstood the point of the book – B Tyler Sep 8 '11 at 5:36 I don't think I have. The book includes a lot of complexity analysis, but it is not about complexity theory in the way that, say, Sipser's book is.

– Adrian Petrescu Sep 8 '11 at 17:08 Personally I prefer to learn from example and see the theory emerge through those examples; after that I find the theory has context rather than being some abstract thing. That's why for me it's a good place to look. – B Tyler Sep 9 '11 at 14:05.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.