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 hal

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/ https://bcmullins.github.io/complexity_theory_resources/.