--- title: Complexity Theory description: Complexity theory classifies computational problems according to their inherent difficulty and the resources required to solve them. Learners will understand the relationships between complexity classes like P, NP, and NP-complete, and how to analyze algorithmic efficiency. category: programming-tech subcategory: theoretical-computer-science difficulty: beginner, intermediate, advanced url: /subject/complexity-theory --- # Complexity Theory Complexity theory classifies computational problems according to their inherent difficulty and the resources required to solve them. Learners will understand the relationships between complexity classes like P, NP, and NP-complete, and how to analyze algorithmic efficiency. ## Available Resources 3 Books • 3 Courses • 4 Websites ## Websites ### 1. 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. **Difficulty:** Beginner | **Price:** Free **Link:** https://scottaaronson.blog/ **Tags:** computational complexity, quantum computing, P vs NP, research blog ### 2. 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. **Difficulty:** Beginner | **Price:** Free **Link:** https://complexityzoo.net/Complexity_Zoo **Tags:** complexity classes, computational complexity, reference, wiki ### 3. 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. **Difficulty:** Beginner | **Price:** Free **Link:** https://nandgame.com/ **Tags:** digital-logic, logic-gates, cpu-design, alu, interactive ### 4. brilliant.org Brilliant.org is an online, interactive learning platform offering problem-based courses in math and computer science, including topics in automata theory, computation, and discrete mathematics, with guided lessons and practice problems. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://brilliant.org **Tags:** websites, technology-computer-science, theoretical-computer-science ## Courses ### 1. 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. **Difficulty:** Advanced | **Price:** Free **Link:** https://cs170.org/ **Tags:** algorithms, NP-completeness, dynamic programming, graph algorithms, UC Berkeley ### 2. Theory of Computation (MIT 18.404J) **Author:** Michael Sipser 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. **Difficulty:** Intermediate | **Price:** Free **Link:** https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/ **Tags:** automata-theory, computability, decidability, complexity-theory, np-completeness ### 3. Advanced Topics in Cryptography (MIT 6.5630) **Author:** Yael Tauman Kalai 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. **Difficulty:** Advanced | **Price:** Free **Link:** https://ocw.mit.edu/courses/6-5630-advanced-topics-in-cryptography-fall-2023/ **Tags:** interactive-proofs, pcp-theorem, snargs, proof-systems, cryptography ## Books ### 1. Introduction to the Theory of Computation (3rd Edition) **Author:** Michael Sipser Sipser's standard text builds automata, Turing machines, decidability, reducibility, Rice-style arguments and complexity from careful definitions and complete proofs. After it you can prove a problem undecidable by reduction and state the Church-Turing thesis precisely. **Difficulty:** Intermediate | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/113318779X?tag=edmonddante07-20 **Tags:** automata-theory, turing-machines, decidability, computational-complexity, formal-languages ### 2. Computational Complexity **Author:** 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. **Difficulty:** Intermediate | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/0201530821?tag=edmonddante07-20 **Tags:** books, technology-computer-science, theoretical-computer-science ### 3. Complexity: A Guided Tour **Author:** 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. **Difficulty:** Intermediate | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/0199798109?tag=edmonddante07-20 **Tags:** books, technology-computer-science, theoretical-computer-science --- *This content is part of Dantes.io - Your Treasure Map to Knowledge* *Curated by humans at Dantes.io. Personal study use welcome; republishing this curation requires permission (team@dantes.io).* View this page online: https://dantes.io/subject/complexity-theory