Complexity: A Guided Tour
by Melanie Mitchell · Melanie Mitchell
Santa Fe Institute researcher's non-technical account of complex systems: cellular automata, genetic algorithms, networks, chaos and information theory. Readers come away understanding how organised behaviour emerges from simple interacting parts across biology and computing.
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.