Complexity Theory
Complexity Theory
Complexity theory classifies computational problems by their inherent difficulty — not the complexity of a particular algorithm, but the minimum resources any algorithm needs. It explains why some problems have fast solutions, others require exponential time regardless of algorithmic cleverness, and a vast class of important problems sits in a frustrating middle ground.
Complexity Classes
Problems are classified by the resources needed to solve them: time (number of steps) and space (memory), measured as a function of input size n.
P contains problems solvable in polynomial time O(nᵏ). Polynomial time is the informal definition of "efficiently solvable": sorting (O(n log n)), shortest paths (Dijkstra's O((V+E) log V)), linear programming (O(n³)), primality testing (O((log n)¹²)).
NP (Nondeterministic Polynomial) contains problems where a "yes" solution can be verified in polynomial time. Whether it can be found in polynomial time is unknown. Given a proposed Sudoku solution, verifying it takes O(n²). Finding it may take exponential time.
Equivalently (and historically): problems solvable by a nondeterministic Turing machine in polynomial time. A NDTM can "branch" on all choices simultaneously and accept if any branch succeeds.
P ⊆ NP (every P problem's solution can be trivially verified). Whether P = NP is the most important open problem in mathematics and computer science.
The P vs NP Question
If P = NP, every problem whose solution is verifiable in polynomial time is also solvable in polynomial time. This would mean: theorem provers could find proofs as easily as check them, protein folding could be solved optimally, most cryptography would break (integer factorization is in NP; if P=NP, RSA collapses).
Most researchers believe P ≠ NP, but it has resisted proof for 50 years. The Clay Mathematics Institute offers $1 million for a resolution.
Cook's Theorem and NP-Completeness
Stephen Cook (1971) proved that 3-SAT is NP-complete: it's in NP (solutions are easily verified), and every NP problem reduces to it in polynomial time.
3-SAT: given a boolean formula in conjunctive normal form with exactly 3 literals per clause, is there an assignment satisfying all clauses?
Since then, thousands of problems have been proven NP-complete by reduction: to prove problem B is NP-complete, find a polynomial-time reduction from a known NP-complete problem A to B. If A ≤ₚ B (A reduces to B), B is at least as hard as A.
Key NP-complete problems:
- Graph coloring: can a graph be colored with k colors so no adjacent vertices share a color? (k ≥ 3)
- Hamiltonian path: does a graph have a path visiting every vertex exactly once?
- Vertex cover: is there a set of k vertices covering all edges?
- Subset sum / Knapsack: given weights/values and a capacity, find the maximum-value selection within capacity
- Traveling Salesman Problem (TSP): shortest tour visiting all cities
- Integer Linear Programming: LP with integer variables
Dealing With NP-Hardness
Encountering an NP-complete problem in practice doesn't mean defeat. Strategies:
Exact algorithms for small instances: dynamic programming over subsets (O(2ⁿ · n)) solves TSP for n ≤ 20-25. Branch and bound prunes the search tree. Practical TSP solvers handle millions of cities using sophisticated cutting planes.
Approximation algorithms: find solutions provably close to optimal. The greedy vertex cover is a 2-approximation (it finds a cover at most twice the optimal size). TSP with triangle inequality has a 1.5-approximation (Christofides algorithm). The theory of APX defines what's approximable within a constant factor.
Parameterized complexity: if the problem is NP-hard in the input size n but tractable when a parameter k is small, use fixed-parameter tractable (FPT) algorithms: runtime O(f(k) · nᶜ). Vertex cover is FPT in the cover size k: O(2ᵏ · n). This is powerful when k is small in practice.
Randomized algorithms: sometimes a randomized algorithm that is correct with high probability and runs in polynomial time (Las Vegas or Monte Carlo algorithms) is acceptable. Some NP problems have randomized polynomial-time algorithms.
Heuristics and metaheuristics: simulated annealing, genetic algorithms, local search. No approximation guarantee, but produce good solutions in practice.
The Complexity Zoo
Beyond P and NP:
coNP: problems whose "no" instances are verifiable in polynomial time. If P ≠ NP, P ≠ coNP. Graph non-isomorphism is in coNP.
PSPACE: problems solvable in polynomial space (memory). PSPACE ⊇ NP (you can solve NP problems using polynomial space). PSPACE-complete problems include game-playing (generalized chess, go).
#P: counting problems — how many solutions exist? Counting satisfying assignments of a 3-CNF formula is #P-complete. Harder than NP (you can determine existence from count, but not the reverse).
BPP: problems solvable in polynomial time with a bounded-error randomized algorithm (error probability < 1/3). Believed to equal P, but unproven. Miller-Rabin primality testing is a BPP algorithm.
Cryptography and Complexity
Most public-key cryptography relies on conjectured hardness. RSA relies on integer factorization being hard (in NP but not known to be NP-complete). ECC relies on discrete logarithm hardness. Post-quantum cryptography uses problems believed hard even for quantum computers (lattice problems, code-based).
Quantum computers can solve factorization in polynomial time (Shor's algorithm, 1994). This doesn't prove P = NP — quantum complexity theory (BQP) is a different complexity class. But it means RSA is broken by sufficiently large quantum computers — the motivation for NIST's post-quantum cryptography standardization (completed 2024).