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, 138 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
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 | ||
Deterministic Turing machine | Abstract machine defining what "computation" and "resource use" mean | ||
Time O(n²), space O(n log n) | Upper limit on time steps or memory cells used by an algorithm | ||
O(n³), Θ(n log n), Ω(2ⁿ) | Describes growth rate of resource usage as input size n → ∞ | ||
Number of bits encoding the input | • Standard measure n • all resource bounds are functions of n | ||
Quicksort worst case O(n²) | • Resource bound over all inputs of length n • the dominant complexity measure |