Why is the class P the same whether you define it on a tape machine or on a random-access machine?
answer
- the class moves, the boundary does not
- each model emulates the other
- overhead is itself polynomial
- polynomial of a polynomial
- fails for linear time and unbounded word width
basics
~20 sBecause each model simulates the other with only polynomial overhead, and a polynomial of a polynomial is still a polynomial. Membership therefore transfers in both directions, even though the exponent changes and finer bounds such as linear time do not survive.
solid answer
~40 sTake an algorithm running in polynomial time on a random-access model. A tape machine can simulate it step for step, paying a polynomial factor for the tape motion that stands in for indexed addressing. Substituting that overhead into the original polynomial gives another polynomial, so the simulated run is still polynomial-time — and the reverse direction is easier still. That argument is the whole reason the class is quoted without naming a model. Two caveats matter. The robustness is a property of **polynomial** time specifically: linear time is model-dependent, since work that is one indexed access on a random-access model can cost a whole pass on a tape. And it assumes a cost model that charges honestly for wide values, not a unit-cost model with unbounded word width.
go deeper
The takeaway is that a polynomial-time result does not have to name the machine it was proved on, because translating between ordinary sequential machines costs only a polynomial factor.
Be able to run the argument: each model simulates the other with polynomial overhead, and substituting one polynomial into another stays polynomial. Note that the exponent is not preserved, only membership.
Show where it stops. Linear-time claims are model-dependent and worth re-checking against the real access pattern, and a cost model that charges one step for work on an unbounded-width value produces bounds that do not mean what they say.
The strategic point is that robustness is what makes complexity results reusable across teams and decades. When you adopt a cost model for your own analyses, make sure it charges for width, or your published bounds will not survive contact with real data.
## The claim, stated precisely The claim is not that all machine models behave alike. It is narrower and it is the narrowness that makes it true: **for reasonable deterministic sequential models with an honest cost per step, the set of problems solvable in polynomial time is the same set.** The running times differ, the exponents differ, sometimes badly — but the boundary of the class does not move. That is why a complexity result can be quoted without saying which machine it was proved on, and why an engineer can reason about a published bound without knowing how the author counted steps. ## The simulation argument in three steps 1. **Each model can simulate the other.** A tape machine can represent a random-access memory as a region of tape and emulate an indexed read by scanning to the right position; a random-access model can emulate tape motion trivially, by keeping an index. 2. **The simulation overhead is itself polynomial.** Emulating one indexed access costs a scan whose length is bounded by the memory touched so far, which after `t` steps is at most polynomial in `t`. Simulating a multi-tape machine on a single tape costs a quadratic factor by the same kind of argument. 3. **Polynomials compose.** If the original cost is `n^k` and each of its steps costs at most `n^j` in the simulator, the simulated cost is at most `n^(k+j)` — still a polynomial. Therefore membership transfers. Step three is doing the real work, and it is the same closure property that makes polynomial time useful for building algorithms out of algorithms. ## What the overhead looks like | going from | to | typical overhead | does class membership change? | |---|---|---|---| | multi-tape machine | single-tape machine | quadratic in the running time | no | | random-access model | tape machine | a fixed polynomial factor | no | | tape machine | random-access model | at most a constant factor | no | Notice the last column is constant and the middle one is not. The exponent is not preserved by any of these translations; only the existence of *some* exponent is. That is the exact sense in which the class is robust. ## Where the robustness stops This is the part that separates a recited answer from an understood one. The claim has boundaries on both sides. - **Below polynomial, it fails.** Linear time is model-dependent. A task that a random-access model completes in one pass with indexed lookups can force a tape machine into repeated head travel, pushing the cost to a higher power. Any statement about linear or near-linear time must name its model; a statement about polynomial time need not. - **Above the honest cost model, it fails.** If a random-access model is allowed to hold unbounded-width values in a cell and to multiply two of them in one step, then repeated squaring packs exponentially many bits into a single value and performs an exponential amount of work per step. Such a model computes far more in 'polynomial time' than any tape machine, and the equivalence collapses. The fix is to charge for width — either bound the cell width or charge a cost proportional to the number of bits touched. - **Outside deterministic sequential computation, it is a different conversation.** Models that add nondeterminism, randomness, parallelism or a fundamentally different physical basis are compared by their own theorems, not by this simulation argument. Do not stretch the claim to cover them. ## Why an engineer should care Three practical consequences fall out of this: - **A published polynomial bound is portable.** You do not need the author's machine model to know the cost curve bends the right way on yours. - **A published linear bound is not.** Near-linear claims are worth checking against the memory-access pattern you will actually have, because the model assumption is load-bearing there. - **A cost model that lies produces bounds that lie.** Counting an operation on an arbitrarily wide value as one step is the same error as measuring input size by value instead of by length: both hide unbounded work inside something that was called a unit. The short version for an interview: the class is robust because simulation overhead between reasonable sequential models is polynomial and polynomials compose; the robustness is specific to polynomial time, and it depends on charging honestly for each step.
- If the class is model-independent, why do published exponents differ between models?Because only the existence of some exponent transfers, not its value. A simulation multiplies the original cost by its own polynomial overhead, so a quadratic algorithm can become quartic after translation. The claim preserved is membership, and nothing finer than that.
- What breaks if a random-access model charges one step for multiplying two arbitrarily wide values?Repeated squaring then doubles the width every step, so after a polynomial number of steps a single value holds exponentially many bits and the model has done exponential work while counting polynomial steps. The equivalence with tape machines fails, so the cost model must either bound the cell width or charge per bit.
- Which weaker bound is not preserved when moving between these models?Linear time. A single indexed access on a random-access model may cost a whole traversal on a tape machine, so a linear-time algorithm there can become superlinear here. Any linear-time claim must state its machine model; a polynomial-time claim need not.
saying these in an interview costs you the question
- Says every machine model gives identical running times.
- Claims the exponent is preserved by the simulation.
- Assumes linear time is model-independent too.
- Counts an operation on an unbounded-width value as one step.
- Extends the robustness claim to nondeterministic or parallel models.
- Justifies robustness only by saying both models are Turing complete.