Polynomial Time and the Machine-Independence of P

A program that reads a million numbers and does a constant amount of work per number is fast. A program that considers every subset of those numbers is not. Both statements are about growth, and the standard way to make them precise is to count steps of an abstract machine as a function of input length. The resulting class, P, is the set of decision problems solvable in a number of steps bounded by a polynomial in the input length. The definition is stated in terms of Turing machines, a model no practitioner uses, and that choice turns out not to matter much. Understanding why it does not matter, and the narrow set of circumstances in which it does, is most of what there is to say about the class.

Steps before halting

A deterministic Turing machine has a finite state set, a finite tape alphabet containing a distinguished blank symbol, an input alphabet drawn from the tape alphabet, and a transition function mapping a state and the symbol under the head to a new state, a written symbol, and a head move. The machine starts with the input written on a tape, in an initial state, and halts when it enters one of two distinguished states. The number of steps taken before halting is the machine’s running time on that input. For a machine that halts on every input, the time complexity is the maximum running time over inputs of length $n$.

$$\mathrm{P} = \bigcup_{k \ge 1} \mathrm{DTIME}(n^k)$$

Three conventions hide inside that line. The machine must halt on every input, so a machine that loops on some input does not define a time bound at all. The bound is worst case over inputs of a given length, not an average. And the length is measured in tape cells, which is to say the encoding of the input matters. Each convention is a decision with consequences, and the last one is where most practical confusion originates.

The class is closed under the operations one expects of a decision class: complement, finite unions and intersections, concatenation, and Kleene star. Closure under complement is immediate, since the halting states can be exchanged. Closure under star requires care with the polynomial degree, because a machine that guesses where to split the input and then runs the inner machine on each part needs to try $n$ split positions, each costing a polynomial, giving a polynomial of degree one higher.

The simulation ledger

The reason P is a natural class rather than an artifact of one machine model is that any two reasonable models simulate each other with polynomial overhead. The simulations are constructive and their costs are known.

A one-tape machine simulates a $k$-tape machine in $O(t^2)$ steps. The construction writes the $k$ tapes onto a single tape, separated by marker symbols, and stores the position of each head by expanding the alphabet: each tape cell carries a symbol from the tape alphabet together with a bit saying whether a head is present. The expanded alphabet has size exponential in $k$, a constant that depends on the machine but not on the input. Each simulated step requires a sweep to the rightmost visited cell and back, because the transition function may need to see all $k$ symbols under the heads, and the visited region has length at most $t$. The cost per simulated step is therefore $O(t)$, and the total is $O(t^2)$.

The reverse direction is cheaper: a $k$-tape machine simulates a one-tape machine in $O(t)$ steps by using one of its tapes for the input and ignoring the rest. A random-access machine with logarithmic cost per operation simulates a Turing machine in linear time by keeping the tape in an array, and a Turing machine simulates such a machine with polynomial overhead by storing registers in binary on the tape and paying a scan for each address decode.

The table of overheads is therefore closed under composition:

Simulating	On	Overhead
$k$-tape machine	one-tape machine	$O(t^2)$
one-tape machine	$k$-tape machine	$O(t)$
logarithmic-cost RAM	Turing machine	$O(t)$
Turing machine	logarithmic-cost RAM	polynomial in $t$
circuit family	Turing machine	polynomial, given a description of the circuit

Composing two simulations multiplies the degrees: if model A simulates model B with overhead $t^c$ and B simulates C with overhead $t^d$, then A simulates C with overhead $t^{cd}$. The degree changes, and P does not notice, because P is a union over all degrees. This is the entire argument for machine independence, and it is worth stating as a rule: any simulation whose overhead is polynomial in the running time preserves P; any simulation whose overhead is exponential in the running time does not.

What the invariance does not cover

The rule has exceptions that are instructive rather than annoying.

Unit-cost arithmetic on unbounded words. If a model charges one step for adding or multiplying two integers of arbitrary length, then a single step can carry out work whose result has length exponential in the input, and a Turing machine needs polynomially many steps to reproduce that result. Simulations in both directions then fail: the fast model decides problems no known polynomial-time Turing machine decides, and the slow model cannot reproduce the fast model’s individual steps within a polynomial factor. Complexity theory therefore charges by the bit. A unit-cost model with fixed-width words is fine, because the word width is a constant that does not grow with the input, so each operation costs a bounded number of Turing machine steps.

Unbounded parallelism. A model that can spawn arbitrarily many processors in one step, each doing a step, is not simulated by a sequential machine in polynomial time in general. The class it defines is not known to equal P and is not believed to. Bounded parallelism, where the number of processors is fixed or grows only polynomially, is fine.

Advice and non-uniformity. A model that receives an extra string depending only on the input length, with no bound on the string’s length, defines non-uniform classes that are not known to coincide with P. A polynomial-length advice string gives the class P/poly, which contains undecidable languages, so it cannot equal P.

Oracles. A machine with a subroutine that answers arbitrary questions about a fixed language in one step defines classes relative to that language. These are the subject of oracle separations and relativization, and they behave differently from P in ways that no simulation argument can paper over.

Encoding, padding, and the meaning of the input length

Complexity is a function of the length of the encoding, so the encoding is part of the problem statement. The clearest illustration is the subset-sum decision problem: given weights and a target, is there a subset whose weights sum to the target? The standard dynamic program fills a table with one row per weight and one column per achievable sum, which is $O(nW)$ where $W$ is the target value.

def subset_sum(weights, target):
    # bit i is set iff some subset sums to i
    reachable = 1
    mask = (1 << (target + 1)) - 1
    for w in weights:
        reachable |= (reachable << w) & mask
    return (reachable >> target) & 1

If the target is written in binary, the input length is about $n \log W$, and $O(nW)$ is exponential in that length. The algorithm is polynomial in the numeric value of the target and exponential in its encoding. Algorithms with this property are called pseudo-polynomial, and the distinction is not pedantry: the same problem is NP-complete when the target is binary, which is the subject of the certificate definition of NP.

The opposite trick is padding. Given a language $L$ over a small alphabet, the padded version ${x#^{|x|^2} : x \in L}$ has length $|x|^2 + |x|$, so a machine running in time proportional to the padded length runs in time proportional to the square of the original length. Padding is how hierarchy theorems produce languages that sit strictly between two time bounds, and it is the reason those theorems are stated with constructible bounds rather than arbitrary functions.

Linear speedup, and why constants carry no information

Any Turing machine can be made faster by a constant factor. The tape compression construction packs $m$ adjacent symbols into one symbol of an expanded alphabet, so a machine that took $t$ steps takes about $t/m$ steps on the compressed tape, at the cost of a linear pass to compress the input and a linear pass to decompress the output. The precise statement is that for every constant $c > 0$, $\mathrm{DTIME}(f(n)) \subseteq \mathrm{DTIME}(f(n)/c + n)$.

The consequence is that the definition of P cannot distinguish $n^2$ from $100n^2$, and it cannot distinguish $n \log n$ from $n$ either, because the class is closed under polynomial changes in the bound. Those distinctions are real and matter in practice, but they have to be made in a finer model than P. What P records is the difference between polynomial and exponential, and that difference is stable under every reasonable change of machine.

Where the class and the intuition separate

P is a coarse instrument, and it is worth being explicit about the ways it fails to match the notion of a feasible computation.

A polynomial of high degree is not feasible. Composing reductions, or composing the simulations above, can produce bounds like $n^{40}$ with large constants. Nothing in the definition forbids it. Conversely, problems outside P can be solved quickly on the inputs that occur, because P is a worst-case class and says nothing about typical inputs, and because a superpolynomial asymptotic bound can still be small for every input of practical size.

Memory is not counted. P bounds time only; a computation may use polynomial space or exponential space and still be in P if its running time is polynomial, since a machine running for $t$ steps visits at most $t$ cells. The separate study of space bounds produces classes that are not known to equal P and, for the smallest bounds, are known to be different from it.

The hierarchy of finer time classes is genuinely infinite: for every constructible bound $f$ there is a language decidable in time $O(f(n) \log f(n))$ but not in $O(f(n))$, as the time hierarchy theorem shows. P is the union of all of them, and the union erases the structure that the individual levels carry.

What survives is a class with three properties that make it the reference point for everything else: it is model-independent, it is closed under the natural operations, and it contains the problems for which a polynomial algorithm is known. Every hardness result in the subject is stated relative to it.