关于这个问题的以下回答正合我意。

https://www.quora.com/What-are-your-favorite-books-on-Complexity-Theory

There are quite a number of good texts on Complexity Theory. For beginners, I would recommend Computational Complexity by Christos H. Papadimitriou. It provides a comprehensive view of the field including Turing machines, Computability, Intractability, boolean circuits and so on.

For undergraduates and who are a little new to this field, I would recommend Introduction to the Theory of Computation by Michael Sipser. This is not a complete text on Complexity theory as it mainly gives an introduction to Time and Space complexity along with brush-ups of Turing machines.

For last half decade or so, Computational Complexity: A Modern Approach by Arora, Barak has become really popular in this domain. This book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. It is fairly comprehensive and has a rich set of problem-sets to solve.

In some universities, Computational Complexity: A Conceptual Perspective by Oded Goldreich has started to serve as a nice reference book. I went through parts of this book and I really liked it.

In summary, If you are beginner in this field, try your hands on Papadimitriou or Sipser. If you feel reasonably comfortable with Turing Machines, computability etc, then Arora Barak will serve you well.