What is a good reference or textbook to introduce oneself to complexity theory?

Question

I am interested in learning some complexity theory, starting from the basics.

Can you recommend some textbooks?

Answer 1

I’ve heard good things about Goldreich’s text, but haven’t used it myself.

Arora—Barak is considered the standard, but I don’t really like it. They make a fair number of errors in their proofs, omit too many details, and the exercises demand too much. The service this book provides is an overview of various areas of complexity, many of which are niche.

For a general introduction to Theory of Computation (Automata, Computability, P vs. NP, basic space complexity), Sipser’s text is quite good. I also like Savage’s text Models of Computation, which spends quite a bit of time on circuits as a model of computation. Chapter 2 of Savage is essentially getting at the NC hierarchy, though Savage doesn’t use that terminology.

Answer 2

Sipser Introduction to the Theory of Computation, very readable. There are video lectures by the author as well, here: https://youtube.com/playlist?list=PLUl4u3cNGP60_JNv2MmK3wkOt9syvfQWY