Same problem. Different machine model. O(n²) vs O(n).
CLO-3R2·30 ptsL9
🔊 Listen
1 · Why a second tape changes everything
The same language {0n1n} that costs a single-tape TM Θ(n²) time (Problem 18) drops to O(n) on a two-tape TM. The strategy: 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. If both tapes hit their end-of-data markers at the same step, accept. If one runs out before the other, reject.
Sipser Theorem 7.8 · the robustness of P
Every k-tape Turing machine running in time t(n) can be simulated by a single-tape TM in time O(t(n)²). Polynomial composed with polynomial is polynomial, so P is invariant under tape count — the class doesn't change when you add or remove tapes.
The single-vs-two-tape gap on {0n1n} is the canonical example of this theorem in action: O(n) vs O(n²), exactly a quadratic blowup.
2 · The two-tape strategy visualised
🔊 Listen
3 · Animated demo · auto-plays · loops
Two tape models racing on the same input Auto-plays
Single-tape · O(n²)
Steps: 0
Two-tape · O(n)
Steps: 0
🔊 Listen
4 · Pitfalls
The simulation is t(n)², not t(n) × k. Simulating a k-tape TM on a single tape costs Θ(t(n)²) — independent of k, because the limiting step is shuttling the single head across all k simulated tapes per simulated step.
P is invariant under tape count — but EXPTIME is too. The robustness theorem actually shows polynomial-bounded classes survive any polynomial blowup. Exponential-time classes also survive.
Two-tape O(n) requires both heads moving independently. If you constrain the heads to move together, you lose the speedup. Independent heads are the whole feature.
🔊 Listen
5 · Q&A defence notes
Q1. Why does two-tape win so much on this problem?
The second tape acts as a scratch register that holds half the data. The two heads then move past each other in parallel, doing the count-comparison in a single sweep instead of n separate sweeps. The mechanism is "free copying" — copy 0s in O(n), then compare in O(n).
Q2. Why doesn't this break P?
The simulation cost is at most a quadratic blowup, and a quadratic blowup of a polynomial is still a polynomial. P is defined to be robust under such blowups precisely because tape count is a model-specific detail.
Q3. What's the limit of multi-tape speedup?
Some problems get a linear speedup (factor n) from extra tapes; some get a polylog speedup; some don't speed up at all. For decision problems, you can usually get a quadratic-to-linear improvement, but not arbitrary speedups — they're bounded below by information-theoretic lower bounds like Ω(n log n) for sorting.
Q4. Is this why we care about the random-access machine (RAM) model?
Yes — RAMs let you address any tape cell in O(1) without shuttling, so they sit at the convenient "what your laptop feels like" point. RAM time is polynomially equivalent to TM time, so theorists use either freely.
🔊 Listen
6 · Where to read more
Sipser: Theorem 7.8 (k-tape ↔ 1-tape simulation), Example 7.2. Lecture notes: Module 4 slide 4 has this exact race. Companion problem: P18 (single-tape Θ(n²) detail).