Complexity theory classifies computational problems by the resources required to solve them—time, space, randomness, or interaction—and studies the relationships between these classes. Computability theory asks a more fundamental question: which problems are solvable at all? Together they form the mathematical bedrock of theoretical computer science, underpinned by the unresolved P vs NP question (a Millennium Prize Problem), landmark results like the Cook-Levin theorem and Savitch's theorem, and a rich hierarchy of classes from L and NL through PSPACE and EXPTIME to the undecidable.
What This Cheat Sheet Covers
This topic spans 16 focused tables and 262 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Foundational Complexity Concepts
| Concept | Example | Description |
|---|---|---|
Is graph G 3-colorable? | Problem with a yes/no answer; the standard model for complexity classification | |
Find a 3-coloring of G | Asks for an explicit witness; often reducible to the decision version | |
Minimize TSP tour length | Asks for the best solution; typically harder than the decision analog | |
Sorting, shortest path (Dijkstra) | Solvable in polynomial time; considered "efficiently computable" | |
General TSP (optimization) | No known polynomial-time algorithm; believed to require super-polynomial time |