complexityzoo.net
Unknown
Complexity Zoo is a comprehensive online catalog of computational complexity classes, providing formal definitions, properties, and the known relationships (inclusions and separations) among classes. It covers hundreds of classes—from P, NP, PSPACE, and EXP to probabilistic, quantum, counting, and nonuniform varieties—along with their definitions and key results, making it a core reference for Theory of Computation.
More resources on Theory of Computation
theoryofcomputing.org
Theoryofcomputing.org is a practical resource hub for theory of computation, featuring lecture notes, tutorials, and problem sets on automata, formal languages, computability, and complexity to help learners build intuition and tackle exercises.
NFA to DFA Converter
Browser-based simulator by Kyle Dickerson for building DFAs, NFAs, and pushdown automata, then running inputs through them singly or in bulk. Useful for checking by hand whether a machine you designed accepts the right language.
Algorithmic Lower Bounds: Fun with Hardness Proofs (MIT 6.890)
Techniques for proving problems computationally hard: NP-hardness reductions, gadget design, games and puzzles, PSPACE-completeness, inapproximability and fixed-parameter hardness. Includes 23 lecture videos, lecture notes, and problem sets with solutions. Afterwards you can construct reductions showing a problem likely has no efficient algorithm.
Introduction to Algorithms (MIT 6.006)
Modeling computational problems and solving them with core algorithms and data structures: sorting, hashing, binary trees, heaps, graph search, shortest paths and dynamic programming. 32 lecture videos, notes, problem sets and exams with solutions teach asymptotic analysis and algorithm design.
Theory of Computation
Learn computability theory with Kamala Krithivasan's Theory of Computation course. Explore fundamental concepts and problem-solving!
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.