Computational Complexity
by Christos H. Papadimitriou · Christos H. Papadimitriou
Graduate textbook building complexity theory from Turing machines through NP-completeness, the polynomial hierarchy, randomized and parallel classes, and circuit lower bounds. Prepares readers to read research papers and construct reductions between hard problems themselves.
This link may earn us a small commission at no extra cost to you. Affiliate disclosure
More resources on Complexity Theory
Scott Aaronson's Blog
Shtetl-Optimized, written by quantum computing theorist Scott Aaronson, posts long arguments about P versus NP, quantum supremacy claims, and open problems. Readers gain a working sense of how complexity researchers actually debate results.
Complexity Zoo
Wiki catalogue of over five hundred computational complexity classes, each with a formal definition, known inclusions and references. Useful for checking what a class such as BPP or PH means and how it relates to others.
CS 170: Efficient Algorithms and Intractable Problems
Learn efficient algorithms and tackle intractable problems with Luca Trevisan's CS 170 complexity theory course. Explore fundamental computer science concepts.
Theory of Computation (MIT 18.404J)
Sipser's course on automata, computability and complexity: regular and context-free languages, decidability, reducibility, the recursion theorem, time and space complexity, NP-completeness, hierarchy theorems, probabilistic computation and interactive proofs. 25 lecture videos, slides, problem sets and exams support rigorous proof-based study.
Advanced Topics in Cryptography (MIT 6.5630)
Research-level study of proof systems: interactive proofs, multi-prover interactive proofs and probabilistically checkable proofs, then how cryptography turns them into succinct non-interactive arguments (SNARGs). 17 lecture videos prepare learners to read current work on delegation and verifiable computation.
NandGame
A browser puzzle that starts with a single NAND gate and has you compose latches, adders, an ALU, memory, and finally a working CPU with its own assembler and instruction set.