A definitive reference
Having explored the fundamental limits of computation itself, we now turn to a more practical question: among problems that can be solved algorithmically, which ones can be solved efficiently? This shift from computability to complexity represents one of the most important developments in theoretical computer science.
While undecidability tells us about absolute impossibility, computational complexity theory addresses the resources required for computation. We introduce time and space as fundamental computational resources, develop mathematical frameworks for measuring efficiency, and establish the foundational complexity classes that organize our understanding of algorithmic difficulty.
This module establishes the mathematical foundations of complexity theory, including resource-bounded computation models, fundamental complexity classes, hierarchy theorems that provide unconditional separations, and deep structural relationships like Savitch's theorem and the Immerman-Szelepcsényi theorem.
The transition from computability to complexity requires precise definitions of computational resources and methods for measuring their consumption during algorithm execution.
A computational resource is any measurable quantity consumed during the execution of an algorithm. The two fundamental resources are:
For a Turing machine M and input x, we define time and space consumption relative to the length |x| of the input.
For a Turing machine M, the time complexity function TM: ℕ → ℕ is defined by:
TM(n) = max{t : M halts on some input x with |x| = n within t steps}
If M does not halt on some input of length n, then TM(n) is undefined. We say M runs in time f(n) if TM(n) ≤ f(n) for all n.
For a Turing machine M, the space complexity function SM: ℕ → ℕ is defined by:
SM(n) = max{s : M uses at most s tape cells on some input x with |x| = n}
For space complexity, we typically count only the work tape cells, not including the input tape (which is read-only) or the output tape (which is write-only).
We say M runs in space g(n) if SM(n) ≤ g(n) for all n.
To understand computational efficiency, we need mathematical tools that capture the essential growth behavior of resource functions while abstracting away implementation details and constant factors.
For functions f, g: ℕ → ℕ:
f(n) = O(g(n)) if ∃c > 0, n₀ ∈ ℕ such that f(n) ≤ c·g(n) for all n ≥ n₀f(n) = Ω(g(n)) if ∃c > 0, n₀ ∈ ℕ such that f(n) ≥ c·g(n) for all n ≥ n₀f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n))f(n) = o(g(n)) if limₙ→∞ f(n)/g(n) = 0A function f(n) has:
f(n) = O(nk) for some constant k ≥ 0f(n) = Ω(cn) for some constant c > 1The class of polynomial-time functions is POLY = ∪k ≥ 0 O(nk).
This distinction is fundamental: polynomial growth represents "efficient" computation, while exponential growth represents "intractable" computation for large inputs.
For any constants a > 1, b > 1, and k ≥ 0:
O(log n) ⊂ O(nk) ⊂ O(an) ⊂ O(n!) ⊂ O(nn)
where ⊂ denotes strict inclusion (the left side grows strictly slower than the right side).
For complexity theory to be meaningful, our results must be robust across different computational models. Fortunately, reasonable models of computation are polynomially related in their efficiency.
A k-tape Turing machine is a tuple M = (Q, Σ, Γ, δ, q0, qaccept, qreject) where:
Q is a finite set of statesΣ is the input alphabetΓ ⊇ Σ is the tape alphabetδ: Q × Γk → Q × Γk × {L,R,S}k is the transition functionq0, qaccept, qreject are special statesThe machine has k independent tapes, each with its own read/write head. One tape typically holds the input, others serve as work space.
A Random Access Machine consists of:
R[0], R[1], R[2], ...Each register can hold an arbitrarily large integer. The cost model assigns:
Let M₁ and M₂ be any two "reasonable" computational models (multi-tape TMs, RAMs, etc.). If M₁ solves a problem in time T(n), then M₂ can solve the same problem in time O(T(n)k)for some constant k.
Similarly, if M₁ uses space S(n), then M₂ uses space O(S(n)).
Let Mk be a k-tape TM running in time T(n). We construct a single-tape TM M₁ that simulates Mk:
Mk:MkMk requires O(T(n)) steps of M₁(to scan the tape), so total time is O(T(n)²).We now formalize the notion of problems solvable within specific time bounds, beginning with deterministic computation.
For a function f: ℕ → ℕ, define:
DTIME(f(n)) = {L : L is decided by some DTM in time O(f(n))}
A function f is time-constructible if there exists a TM that, on input 1n, outputs the binary representation of f(n) in time O(f(n)).
Most "natural" functions (polynomials, exponentials, etc.) are time-constructible.
The class P (polynomial time) is defined as:
P = ⋃k ≥ 1 DTIME(nk)
Equivalently, P is the class of languages decidable by a deterministic Turing machine in polynomial time.
P represents the class of "efficiently solvable" problems in the deterministic setting.
Nondeterministic computation provides a powerful abstraction that captures the complexity of many important computational problems.
A nondeterministic Turing machine (NTM) is defined like a DTM, except the transition function has the form:
δ: Q × Γ → P(Q × Γ × {L,R,S})
where P(·) denotes the power set. At each step, the machine may have multiple possible transitions and can "choose" any of them.
An NTM accepts input x if there exists at least one sequence of nondeterministic choices leading to the accept state.
The running time is the maximum number of steps in any accepting computation path.
For a function f: ℕ → ℕ:
NTIME(f(n)) = {L : L is decided by some NTM in time O(f(n))}
The class NP (nondeterministic polynomial time) is:
NP = ⋃k ≥ 1 NTIME(nk)
A language L ⊆ Σ* is in NP if and only if there exist:
p(n)V (the verifier)such that for all x ∈ Σ*:
x ∈ L ⟺ ∃c ∈ Σ{p(|x|)} : V(x,c) = 1
The string c is called a certificate or witness for x.
The nondeterministic Turing machine definition of NP and the certificate-based definition are equivalent.
(⇒) Suppose L ∈ NP via NTM M running in time nk.
Define the certificate c for input x to be the sequence of nondeterministic choices made by M in an accepting computation on x. Since M runs for at most |x|k steps, |c| ≤ |x|k.
The verifier V(x,c) simulates M on x using the choices in c, accepting iff this simulation reaches M's accept state.
(⇐) Suppose L has verifier V and polynomial p.
Construct NTM M that on input x:
c of length p(|x|)V(x,c) and accepts iff V acceptsM accepts x iff there exists c such that V(x,c) = 1, which holds iff x ∈ L.
The hierarchy theorems provide some of the few unconditional separation results in complexity theory, showing that more time genuinely allows for solving more problems.
If f, g: ℕ → ℕ are time-constructible functions such thatf(n) log f(n) = o(g(n)), then:
DTIME(f(n)) ⊊ DTIME(g(n))
In particular, DTIME(nk) ⊊ DTIME(nk+1) for any k ≥ 1.
We use diagonalization. Define the language:
D = {⟨M⟩ : M is a TM that rejects ⟨M⟩ within g(|⟨M⟩|) steps}
Claim 1: D ∈ DTIME(g(n))
Proof: The algorithm for D on input ⟨M⟩:
g(|⟨M⟩|) (possible since g is time-constructible)M on ⟨M⟩ for at most g(|⟨M⟩|) stepsM rejects within this time limitThis runs in O(g(n)) time.
Claim 2: D ∉ DTIME(f(n))
Proof: Suppose D ∈ DTIME(f(n)) via machine M₀. Since f(n) log f(n) = o(g(n)), for sufficiently large n, we have f(n) < g(n)/log f(n).
The simulation overhead in step 2 above is at most log f(n) per step (to maintain the simulation state), so M₀ on ⟨M₀⟩ completes within g(|⟨M₀⟩|) steps of the simulation.
Now consider what happens when we run the algorithm for D on ⟨M₀⟩:
M₀ accepts ⟨M₀⟩, then ⟨M₀⟩ ∈ D, but ⟨M₀⟩ ∉ D by definitionM₀ rejects ⟨M₀⟩, then ⟨M₀⟩ ∉ D, but ⟨M₀⟩ ∈ D by definitionThis contradiction shows D ∉ DTIME(f(n)).
If f, g: ℕ → ℕ are time-constructible functions such thatf(n+1) = o(g(n)), then:
NTIME(f(n)) ⊊ NTIME(g(n))
The gap condition is tighter than for the deterministic case due to the additional complexity of nondeterministic simulation.
Space complexity studies the memory requirements of computation. Unlike time, space can be reused, leading to different mathematical properties and separation results.
For a function s: ℕ → ℕ with s(n) ≥ log n:
DSPACE(s(n)) = {L : L is decided by some DTM using space O(s(n))}
Space is measured as the maximum number of work tape cells used during any computation, not counting the input tape (read-only) or output tape (write-only).
The constraint s(n) ≥ log n ensures sufficient space to maintain a position counter for the input tape.
The class L (logarithmic space) is defined as:
L = DSPACE(log n)
Problems in L can be solved using only logarithmic workspace, which is remarkably restrictive - it's not even enough space to make a copy of the input.
Example problems in L: determining if a number is a power of 2, palindrome checking, graph connectivity in undirected graphs.
The class PSPACE (polynomial space) is defined as:
PSPACE = ⋃k ≥ 1 DSPACE(nk)
PSPACE contains problems solvable using polynomial workspace. This includes many problems involving game-playing, planning, and logical reasoning.
Examples: Quantified Boolean Formula (QBF), determining winning strategies in games, regular expression matching with backreferences.
Nondeterministic space complexity exhibits different behavior from nondeterministic time, as demonstrated by fundamental results like Savitch's theorem.
For s(n) ≥ log n:
NSPACE(s(n)) = {L : L is decided by some NTM using space O(s(n))}
The class NL (nondeterministic logarithmic space) is:
NL = NSPACE(log n)
The canonical NL-complete problem is PATH: given a directed graph and vertices s, t, is there a path from s to t?
Savitch's theorem shows that nondeterminism provides at most a quadratic advantage for space complexity, in stark contrast to the time complexity case where the relationship between P and NP remains open.
For any space-constructible function s(n) ≥ log n:
NSPACE(s(n)) ⊆ DSPACE(s(n)²)
In particular, NL ⊆ L² and NPSPACE = PSPACE.
Let M be an NTM using space s(n). The number of possible configurations of M on input of length n is at most cs(n)for some constant c.
We'll solve the problem by determining if there's a path in the configuration graph from the initial configuration to an accepting configuration.
Algorithm PATH(C₁, C₂, i): Returns true iff there's a path from configuration C₁ to configuration C₂ in at most 2i steps.
i = 0: return true iff C₁ = C₂ or C₁ ⊢ C₂ (direct transition)i > 0: for each possible configuration Cmid:Cmid is found, return falseMain algorithm: Run PATH(C₀, Caccept), ⌈s(n)⌉) where C₀ is the initial configuration and Caccept is any accepting configuration.
Space analysis: The recursion depth is ⌈s(n)⌉, and at each level we need space to store O(s(n)) configurations. Total space: O(s(n)²).
Correctness: PATH(C₁, C₂, i) correctly determines reachability in2i steps by divide-and-conquer on the path length.
Important corollaries of Savitch's theorem:
NL ⊆ DSPACE(log² n)NPSPACE = PSPACE (nondeterminism doesn't help for polynomial space)O(log² n) spaceLike time complexity, space complexity admits hierarchy theorems showing that more space allows solving more problems.
If f, g: ℕ → ℕ are space-constructible functions withf(n) = o(g(n)) and g(n) ≥ log n, then:
DSPACE(f(n)) ⊊ DSPACE(g(n))
A function s is space-constructible if there exists a TM that on input 1n uses exactly s(n) space and halts.
The proof uses diagonalization, but differs from the time hierarchy due to space reusability.
Define language D as follows. On input ⟨M,1n⟩:
|⟨M,1n⟩| ≠ n, rejectM on ⟨M,1n⟩ using space g(n)M accepts and uses space ≤ f(n), rejectClaim: D ∈ DSPACE(g(n)) but D ∉ DSPACE(f(n)).
The proof that D ∈ DSPACE(g(n)) is straightforward from the algorithm.
For D ∉ DSPACE(f(n)), suppose M₀ decides D in space f(n). Then ⟨M₀,1n⟩ ∈ D iff M₀ rejects ⟨M₀,1n⟩ or uses > f(n) space, leading to a contradiction by diagonalization.
Understanding the relationships between different complexity classes provides crucial insight into the structure of computational complexity.
The following inclusion chain holds:
L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE
It is known that L ⊊ PSPACE, but the strictness of the intermediate inclusions remains open (though widely conjectured to be strict).
L ⊆ NL: Any deterministic log-space algorithm is also a nondeterministic log-space algorithm (that makes no nondeterministic choices).
NL ⊆ P: By Savitch's theorem, NL ⊆ DSPACE(log² n). Any algorithm using space s(n) runs in time 2O(s(n)), so DSPACE(log² n) ⊆ DTIME(2O(log² n)) = DTIME(nO(log n)) ⊆ P.
P ⊆ NP: Any deterministic polynomial-time algorithm is also a nondeterministic polynomial-time algorithm.
NP ⊆ PSPACE: Given an NP problem with polynomial-time verifier V, we can solve it in polynomial space by enumerating all possible certificates and running V on each. This requires polynomial space but potentially exponential time.
Fundamental relationships exist between time and space complexity, with some problems admitting tradeoffs between these two resources.
A time-space tradeoff for a problem is a relationship of the form: any algorithm solving the problem with time T must use spaceS ≥ f(n,T), or vice versa.
Such tradeoffs demonstrate fundamental computational limits beyond worst-case analysis in a single resource dimension.
For any language L:
L ∈ DTIME(T(n)), then L ∈ DSPACE(T(n))(an algorithm can't use more space than time)L ∈ DSPACE(S(n)) with S(n) ≥ log n, then L ∈ DTIME(2O(S(n)))(space-bounded algorithms have exponential time bounds)One of the most surprising results in complexity theory shows that nondeterministic space classes are closed under complement, unlike the situation for nondeterministic time.
For any complexity class C, its complement class is:
co-C = {L : L̅ ∈ C}
where L̅ denotes the complement of language L.
Examples: co-NP, co-NL. We always have P = co-P and PSPACE = co-PSPACE.
For any space-constructible function s(n) ≥ log n:
NSPACE(s(n)) = co-NSPACE(s(n))
In particular, NL = co-NL.
We prove NL = co-NL; the general case follows similarly. It suffices to show that co-NL ⊆ NL.
Let L ∈ co-NL, so L̅ ∈ NL. We'll construct an NL algorithm for L.
Consider the canonical NL-complete problem NON-PATH: given a directed graph G and vertices s,t, is there no path from s to t?
Key insight: Use an inductive counting argument. For i = 0, 1, ..., n, let Ci be the number of vertices reachable from s in exactly i steps.
Algorithm for NON-PATH:
C₀ = 1 (only s is reachable in 0 steps)i = 1 to n:CiCi vertices are reachable in ≤ i stepsCi - Ci-1 new vertices are reachable in exactly i stepst is not among the vertices reachable in ≤ n stepsVerification step: To verify that exactly k vertices satisfy property P:
k verticesPv, verify that if v satisfies P, then v is among the guessed verticesSpace analysis: At each step, we need O(log n) space to store counts and current vertex positions. The total space remains O(log n).
Correctness: The algorithm accepts iff there are exactly Cn vertices reachable from s and t is not among them, which is equivalent to no path existing.
The Immerman-Szelepcsényi theorem has several important consequences:
NL (previously only known to be in co-NL)