We have a precise class, \mathrm{P} = \bigcup_k \mathrm{DTIME}(n^k) — the problems a deterministic Turing machine solves in polynomial time. But precision is not the same as meaning. Why should this particular mathematical fence — polynomial on one side, everything else on the other — be the line between problems we call tractable ("we can actually solve these") and intractable ("give up, or cheat")? That identification, P = feasible, is a modelling choice, and one of the most consequential and most debated in all of computer science.

This page is about that choice: the thesis that makes it, the very real objections to it, and why — objections and all — it remains the right place to draw the line.

The Cobham–Edmonds thesis

In the mid-1960s Alan Cobham and Jack Edmonds independently proposed identifying the "efficiently solvable" problems with \mathrm{P}. Edmonds called a polynomial-time algorithm a "good algorithm"; the idea has been the working definition of tractability ever since.

Like the Church–Turing thesis, this is not a theorem to be proved but a claim about how a formal notion (membership in \mathrm{P}) captures an informal one (real-world feasibility). Its justification is partly empirical and partly structural — and it comes with genuinely uncomfortable caveats, which honesty demands we meet head-on.

Why the polynomial line is the right one

The case rests on the staggering gap between polynomial and exponential growth. A polynomial's value rises steadily; an exponential's explodes. The table makes the difference visceral: it lists, for growing input size n, the wall-clock time of algorithms running at one billion operations per second.

Read the 2^n column and feel the cliff: at n = 30 it is a heartbeat, at n = 50 it is a holiday, and at n = 100 it is roughly three thousand times the current age of the universe. Meanwhile n^3 at n = 100 is a single millisecond. Buying a computer a thousand times faster shifts the exponential frontier by a piddling \log_2 1000 \approx 10 in n; it multiplies the polynomial-solvable size by a constant factor. Hardware helps polynomials and taunts exponentials.

There is a structural reason too, and it is the deciding one: \mathrm{P} is closed under composition. A polynomial of a polynomial is a polynomial. That is exactly the property "feasible" ought to have — if a feasible subroutine is called by a feasible outer procedure, the whole thing should still be feasible — and no smaller class (say, "linear time") enjoys it.

Closure under composition, precisely

Suppose procedure A runs in time O(n^a) and calls procedure B, which runs in time O(m^b) on an input of size m. Even in the worst case where A makes O(n^a) calls to B, each on data of size at most polynomial in n, the total is a product and sum of polynomials — still a polynomial in n.

This closure is what lets us reason about large systems modularly: prove each piece polynomial, glue them however you like, and the whole remains in \mathrm{P}. It is the algorithmic analogue of "a function built from continuous functions is continuous" — a robustness that makes the class pleasant to work with.

P is robust across machine models

A worry: our whole definition rode on the Turing machine. Wouldn't a different model — a real RAM, a multi-tape TM, a parallel machine — give a different P? The answer, and it is the second pillar under the thesis, is essentially no.

A one-tape TM simulates a k-tape TM with only a quadratic blow-up; a TM simulates a RAM with polynomial overhead; and so on. Since P is closed under composition, a polynomial blow-up on top of a polynomial algorithm is still polynomial — so all these models agree on exactly which problems are in P. This model-independence is precisely why P, and not some finer class like \mathrm{DTIME}(n^2), is the natural home of "tractable": the finer class would change every time you changed machines.

Problems that live in P

The class is enormously rich — most of the algorithms you already know are witnesses that their problem is in \mathrm{P}:

• Sorting — O(n\log n), comfortably polynomial.
• Shortest paths — Dijkstra's algorithm, O((V+E)\log V).
• Searching — binary search, O(\log n).
• Primality testing — the AKS algorithm (2002) settled that \textsc{Primes} \in \mathrm{P}, a celebrated deterministic \tilde{O}(n^6) result.
• Linear programming — polynomial via the ellipsoid and interior-point methods, despite the exponential-worst-case simplex method being what everyone actually runs.
• Maximum matching, 2-colourability, string matching, matrix multiplication — all in P.

Contrast these with the NP-hard problems — travelling salesman, SAT, graph colouring — for which no polynomial algorithm is known and (if \mathrm{P} \ne \mathrm{NP}) none exists. The boundary between these two worlds is the practical heart of complexity theory.

The honest caveats

The thesis is a convenient idealisation, not a law of nature, and it leaks at the edges. A good complexity theorist states the objections louder than the critics do:

So why keep the definition? Because in practice the exceptions are exactly that — exceptions. When a natural problem is first shown to be in \mathrm{P}, the exponent and constants are almost always soon whittled down to something practical; a genuinely useful O(n^{100}) algorithm for a real problem has essentially never appeared. The thesis works because reality is kind: the polynomial line, drawn for theoretical robustness, turns out empirically to track feasibility remarkably well. It is the best simple definition we have — right far more often than it is wrong.