As someone else said already: Theory of Computation by Sipser is the go to intro book for this.

I'd recommend really reading the book front to back honestly. It helps to have a complete picture of everything that leads up to getting into complexity theory.

Sipser also has corresponding lectures that are available for free on YouTube here: https://www.youtube.com/watch?v=9syvZr-9xwk&list=PLidiQIHRzp....

Scott Aaronson’s Quantum Computing Since Democritus is a clear, entertaining explanation of computational complexity theory as applied to both classical and quantum computers. I thoroughly enjoyed the book, and have recommended it to a number of friends.

https://www.amazon.com/Quantum-Computing-since-Democritus-Aa...

I believe I used Introduction to the Theory of Computation by Sipser for this and it's probably the one textbook most universities are going to use.

Maybe for more in depth reference about the algorithms at play Introduction to Algorithms (Cormen) will complement nicely; I don't remember how much Sipser goes into describing the algos.

Books I have and recommend:

Introduction to the theory of computation - Michael Sipser

Computational complexity - Arora, Barak

Computational Complexity - Christos H. Papadimitriou

Computers and intractability - Michael R. Garey, David S. Johnson

Here's some more specific recommendations from the books people have mentioned:

* Part 3 of Sipser’s Introduction to the Theory of Computation

* The first half of Arora and Barak's Computational Complexity

No one had mentioned this one yet, but it provides nice exposition: Goldreich’s Computational Complexity: a Conceptual Perspective.

Here are some notes I put together on what's out there for learning complexity theory and a bit on where you can go next: https://bcmullins.github.io/complexity_theory_resources/.

The Dragon Book for Compilers

[dead]