Measuring Computational Resources
Decidability asks whether a problem can be solved. Computational complexity asks how efficiently it can be solved — measured in terms of the time (number of computation steps) and space (amount of memory) a Turing machine requires as a function of the input size. This shift from existence to efficiency is what makes complexity theory so practically important.
The time complexity of a Turing machine M is a function t: ℕ → ℕ where t(n) is the maximum number of steps M uses on any input of length n. M runs in time t(n). Analogously, the space complexity s(n) is the maximum number of tape cells used on any input of length n.
Big-O Notation
Big-O notation is the standard tool for expressing asymptotic growth rates — capturing how resource usage scales with input size while ignoring constant factors and lower-order terms.
f(n) = O(g(n)) if there exist constants c > 0 and n₀ ≥ 0 such that f(n) ≤ c · g(n) for all n ≥ n₀. Informally, f grows no faster than g asymptotically.
- O(1) — Constant: array index lookup.
- O(log n) — Logarithmic: binary search.
- O(n) — Linear: scanning a list.
- O(n log n) — Linearithmic: merge sort, heapsort.
- O(n²) — Quadratic: bubble sort, naive matrix operations.
- O(nᵏ) — Polynomial (for constant k): all are considered "efficient" in theory.
- O(2ⁿ) — Exponential: brute-force subset enumeration. Grows catastrophically fast.
Image: Wikimedia Commons, CC BY-SA 4.0
Complexity Classes: P and NP
The most important complexity classes are defined by placing polynomial-time bounds on Turing machine computation. Polynomial time is used as the formal threshold for "efficient" computation because polynomial functions compose well under algorithm combination, and because the gap between polynomial and exponential growth is so large in practice.
P (deterministic polynomial time) is the class of all decision problems solvable by a deterministic Turing machine in time O(nᵏ) for some constant k. These are the problems we consider tractable — solvable in practice for large inputs. Examples: primality testing, shortest path, sorting, 2-SAT.
NP (nondeterministic polynomial time) is the class of all decision problems for which a proposed solution (called a certificate or witness) can be verified in polynomial time by a deterministic TM. Equivalently, NP is the class of problems solvable in polynomial time by a nondeterministic Turing machine. Every problem in P is also in NP.
- Boolean Satisfiability (SAT): Given a Boolean formula, is there a variable assignment making it true? Verifying a proposed assignment is easy (polynomial); finding one is believed to be hard.
- Hamiltonian Cycle: Does a graph contain a cycle visiting every vertex exactly once? Checking a proposed cycle takes O(n) time; finding one seems to require exponential search.
- Travelling Salesman (decision): Is there a route visiting all cities with total cost ≤ k? A proposed route is trivially verified; finding the optimal one is computationally hard.
Image: Wikimedia Commons, CC BY-SA 4.0
NP-Completeness and Reductions
Within NP there is a special subset of problems that are in a precise sense the hardest problems in the class. These are the NP-complete problems: solving any one of them in polynomial time would immediately yield polynomial-time algorithms for every problem in NP.
A problem X is NP-complete if: (1) X ∈ NP, and (2) every problem in NP is polynomial-time reducible to X (X is NP-hard). A polynomial-time reduction from A to B is a computable function f, runnable in polynomial time, such that w ∈ A ⟺ f(w) ∈ B.
Stephen Cook proved in 1971 that SAT (Boolean satisfiability) is NP-complete — this is the Cook-Levin theorem. Richard Karp then showed in 1972 that 21 other natural combinatorial problems are also NP-complete by polynomial reductions from SAT. Thousands more have since been identified.
- 3-SAT: Is a Boolean formula in 3-conjunctive normal form satisfiable? The canonical NP-complete problem from which many other reductions are built.
- Graph Colouring: Can a graph's vertices be coloured with k colours so no two adjacent vertices share a colour? NP-complete for k ≥ 3.
- Clique: Does a graph contain a complete subgraph of size k?
- Knapsack: Can a selection of items with given weights and values fit within a weight limit while exceeding a value threshold?
- Vertex Cover: Does a graph have a set of k vertices that touches every edge?
The P vs. NP Question
The central open problem in computer science — and one of the Clay Millennium Prize Problems worth $1,000,000 — is: does P = NP? That is, if a problem's solution can be verified quickly, can it also be found quickly?
The overwhelming consensus among researchers is that P ≠ NP: that there are problems in NP which provably require super-polynomial time to solve. But despite decades of effort by the world's best mathematicians and computer scientists, no proof exists in either direction. The question remains wide open.
- Cryptography: Modern encryption (RSA, elliptic curves) relies on the presumed hardness of problems like integer factorisation. If P = NP, most encryption schemes would collapse.
- Optimisation: A vast number of real-world scheduling, routing, and resource allocation problems are NP-complete. P = NP would make them tractable.
- AI and proof search: Many AI tasks — planning, theorem proving — are NP-hard or harder. Their tractability hinges on this question.
- Mathematics itself: Since finding proofs can be modelled as an NP problem and verifying them is in P, P = NP might in principle automate mathematical discovery.
Beyond P and NP: Other Complexity Classes
P and NP are the most famous classes, but complexity theory defines a rich landscape of others. co-NP contains the complements of NP problems. PSPACE captures problems solvable in polynomial space (regardless of time), and contains both P and NP. EXPTIME (exponential time) and EXPSPACE sit above these. The study of how all these classes relate — which inclusions are strict, and which might coincide — is the heart of modern complexity theory.