Counting steps on a tape — and watching the same problem in radically different time on different machines.
BCS 402 · Dr. Arash Kermani · CUD
🎧 Narration
1 · Watch growth rates race
The vertical scale grows much faster for exponential curves than for polynomials. The class P consists of problems whose running time stays below some polynomial — that's why P is the central "tractable" class.
Complexity classes are about asymptotic growth: how fast the running time grows as
the input gets large. Watch six functions race.
Growth-rate animator Widget 1 · Auto-plays
n 0
log n 0
n² 0
2ⁿ 0
log nnn log nn²n³2ⁿ
What to watch
Press ▶ Play race. Six curves climb at very different speeds. Pay attention to two moments: (a) when does the exponential curve 2ⁿ overtake the polynomial n³ — usually around n = 9. (b) Notice how log n stays nearly flat — that is the dream complexity. The log scale on the Y-axis compresses huge numbers; switch to linear if you want to feel the chasm in absolute terms.
🔊 Key idea
Polynomial growth (left side) lives in P. Exponential (right) doesn't.
The race makes the gap visible: at n = 40, the gap between n² and 2ⁿ is roughly a trillion-fold.
🎧 Narration
🔊 Big-O picture
Big-O notation discards constants and lower-order terms. The dominant term defines the complexity class. For n=1000, the n² term is 3,000,000 while the linear and constant terms total 105,000 — the quadratic term is what matters asymptotically.
2 · Big-O — what we throw away
Big-O notation says: ignore constants and lower-order terms; keep only the dominant behavior.
The widget below shows what gets thrown away as n grows.
Big-O decomposition Widget 2
What you see
The three stacked colored bands show how the function breaks into pieces. As n grows,
the dominant n² term swallows everything.
🎧 Narration
3 · How a TM spends time on {0ⁿ1ⁿ}
The canonical first example: deciding whether a string has the form
0n1n — equal numbers of 0s and 1s, all 0s before
all 1s. Watch a single-tape TM do this by repeatedly crossing off matched pairs.
Single-tape TM on {0ⁿ1ⁿ} · animated Widget 3 · Auto-plays
Step 0
State q0
Verdict —
Phase
The TM strategy: find leftmost 0, mark it X; sweep right to find leftmost 1, mark it Y; rewind; repeat. If a pass finds no 0 left, check there are no 1s left either.
🔊 Counting steps
Counting steps: each "pair" pass costs O(n) sweeps. There are n/2 pairs. Total: O(n²)
on a single tape. Watch the step counter — it grows quadratically with input length.
🎧 Narration
4 · The model matters — single vs two tapes
On a single-tape TM, deciding 0ⁿ1ⁿ requires the head to bounce back and forth, paying O(n²) time. With a second tape, the same task runs in linear time. The Hennie–Stearns theorem guarantees the gap is at most quadratic — multi-tape TMs are not more powerful, just more efficient by a polynomial factor.
Same language {0n1n}, two TMs side by side:
one with a single tape, one with two tapes. Watch how the two-tape TM finishes in O(n) while
the single-tape one drags on in O(n²).
Two TM models, one race Widget 4 · Auto-plays
Single-tape TM (one head)
Steps: 0
Two-tape TM (two heads)
Steps: 0
The two strategies
Single-tape: shuttle to pair off 0s with 1s, O(n²). Two-tape: copy the 0s to tape 2, then march tape 1 right through the 1s while tape 2 marches left through the copied 0s — both in sync. O(n).
🔊 Theorem
Theorem (Sipser §7.2)
Every k-tape TM running in time t(n) can be simulated by a
single-tape TM running in time O(t(n)2). So polynomial
stays polynomial across reasonable models — the class P is robust.
🎧 Narration
5 · The class P
P = ⋃k ≥ 1 TIME(nk)
A language is in P if some TM decides it in time polynomial in the input
length. Sipser §7.2 highlights three classic, non-trivial examples — pick a toggle in the
widget below and watch each algorithm run.
PATH · graph reachability
PATH = {⟨G, s, t⟩ : G has a directed path s → t}
Why is it in P? Naive "try every path" blows up — there can be exponentially many paths. Algorithm: BFS from s. Touch each vertex and edge at most once. O(|V| + |E|) ⇒ polynomial.
Sipser Theorem 7.14.
RELPRIME · Euclid's algorithm
RELPRIME = {⟨a, b⟩ : gcd(a, b) = 1}
Why is it in P? Input size is the number of digits — log of the values. Algorithm: gcd(a, b) = gcd(b, a mod b) until the second is 0. Each step at least halves the smaller. O(log min(a,b)) divisions ⇒ polynomial in the bit-length.
Sipser Theorem 7.15.
ACFG · CYK parsing
ACFG = {⟨G, w⟩ : G generates w}
Why is it in P? Module 1's enumerate-derivations bound was exponential. Algorithm: CYK (Cocke–Younger–Kasami) — dynamic programming. Fill T[i, j] = "vars deriving wi…wj" bottom-up. O(n³ · |G|) ⇒ polynomial.
Sipser Theorem 7.16.
Classic P problems Widget 5
🔊 Cobham–Edmonds
The Cobham–Edmonds thesis. "Polynomial time" is the right mathematical proxy for
"feasibly computable in practice." It is robust across models, closed under composition, and
matches our experience with real algorithms.
🎧 Narration
6 · Practice (Sipser §7.1–§7.2)
Sipser 7.1
True or false: 5n² + 3n + 2 = O(n²)? True or false: 5n² + 3n + 2 = O(n)?
Show answer
First true (n² dominates). Second false (the n² term grows faster than any constant multiple of n).
Sipser 7.4
Show that the language A = {02k : k ≥ 0} is in P.
Show solution outline
Read input; check all symbols are 0; count length n in unary; check n is a power of 2 by repeatedly dividing by 2. Each check is linear or O(log n); total O(n).
Sipser 7.6
Let UNARY = {1n : n ≥ 1}. Show UNARY ∈ P and that the standard binary representation of n has only ⌈log2(n+1)⌉ bits — so problems with unary inputs are exponentially easier than the same problems with binary inputs.
Show solution outline
Scanning O(n) symbols is polynomial in input length n. The same n in binary takes only log(n) bits, so the binary algorithm would be exponential in input length.
Sipser 7.10
Show that P is closed under union, concatenation, and complement.
Show solution outline
Closed under complement: flip the decider's accept/reject. Closed under union: run both deciders, accept if either accepts. Closed under concatenation: try all splits w = uv and run deciders on u, v; n+1 splits times polynomial = polynomial.
Sipser 7.11
Let TRIANGLE = {⟨G⟩ : G contains a triangle}. Show TRIANGLE ∈ P.
Show solution outline
Enumerate all triples of vertices (u, v, w) and check whether all three edges (u,v), (v,w), (u,w) exist. O(n³) checks of O(1) each.
🎧 Narration
One-sentence summary
🔊 Summary
P is the class of decision problems solvable in polynomial time on a deterministic TM; it is
robust across reasonable machine models, and it is the mathematical proxy for "feasible."