The Class P: Efficiently Solvable

From counting steps to naming a class

You already carry two tools from this rung. First, you know how to measure a machine's running time as the number of steps it takes on the WORST input of each size n, not the average or the lucky case. Second, you can read a growth rate through big-O glasses, which throw away constants and low-order terms and keep only how fast the cost balloons as n grows. This guide spends those two tools on one purpose: drawing a single, sharp line that separates the problems we call 'efficiently solvable' from the ones we do not.

Here is the line. A decision problem (one with a yes/no answer) is in the class P if some deterministic Turing machine — the endless-notebook machine you met on an earlier rung, a head that reads, erases, and rewrites cells one at a time — DECIDES it (always halts with the right yes/no) in time bounded by a polynomial in the input size. 'Polynomial' means the step count is O(n^k) for some FIXED exponent k: O(n), O(n log n), O(n^2), O(n^3), and so on are all allowed, but 2^n is not. That is the whole definition of P. Everything else in this guide is unpacking why this particular line is worth drawing.

Why polynomial beats exponential, in numbers

Why pick polynomial as the dividing line and not, say, 'anything under a billion steps'? Because the polynomial-versus-exponential gap is not a matter of degree — it is a wall. A polynomial like n^3 grows by a constant FACTOR when you double n (doubling n multiplies n^3 by 8). An exponential like 2^n grows by SQUARING-scale leaps — adding ten to n multiplies the cost by about a thousand. No clever constant, no faster chip, can paper over that. Doubling your computer's speed lets a 2^n algorithm handle just ONE more unit of input. This blunt fact is the heart of intractability.

input size n        n^2          n^3            2^n
   10              100          1,000          ~1,000
   20              400          8,000          ~1,000,000
   50            2,500        125,000          ~10^15
   100          10,000      1,000,000          ~10^30

At a billion (10^9) steps per second:
   2^100 steps  ~  10^30 / 10^9  =  10^21 seconds
               ~  30,000,000,000,000 years
   n^3 at n=100 =  1,000,000 steps  =  0.001 second

Look at the table and the choice defends itself. At n = 100 an n^3 algorithm finishes in about a millisecond, while a 2^n algorithm needs more seconds than the universe has had. This is what exponential blowup means in practice: not 'slow', but 'will never finish in any human or cosmic timescale once n is even modest'. Polynomials, however large the exponent, eventually fall below any fixed exponential. So 'in P' is a promise that the cost grows in a way speed-ups and patience can keep up with; 'only exponential algorithms known' is a warning that they cannot.

Who lives in P: the familiar workhorses

P is not an abstract club — it is crowded with problems you would call routine. Graph reachability: given a network of nodes and a start and goal, is there a path between them? A breadth-first search marks the start, then everything one hop away, then two hops, and so on; it touches each node and edge at most a constant number of times, so it runs in time linear in the size of the graph — solidly polynomial. Sorting a list of n items is O(n log n) with mergesort, comfortably polynomial. Shortest paths with non-negative edge weights yield to Dijkstra's algorithm in roughly O(n^2) or better. Each of these is a card-carrying member of P.

The most celebrated entry is PRIMES: given an integer N, is it prime? For decades people had fast methods that were either randomized or unproven, but it was an open question whether a guaranteed, deterministic polynomial-time test existed. In 2002 the AKS algorithm settled it: PRIMES is in P. A crucial subtlety lives here, and it is exactly the input-size lesson from guide 1. The input size of N is the number of DIGITS it takes to write N, about log N, NOT the value of N itself. An algorithm that 'just tries every divisor up to N' runs in time proportional to N, which is 2^(number of digits) — exponential in the input size, not polynomial. Confusing the value with the number of digits is the single most common way to mislabel a number-theory algorithm.

Why P is robust: it barely cares what machine you use

A fair worry: doesn't 'polynomial time' depend on the fussy details of the Turing machine? If I let it have a second tape, or a random-access memory, or write a program in a real language instead, won't the step count change? It does change — but only by a polynomial FACTOR, and a polynomial of a polynomial is still a polynomial. That is the quiet miracle that makes P worth defining. Convert a k-tape machine to a single-tape one and an O(t) computation becomes at worst O(t^2); a polynomial squared is still polynomial. So P is the SAME class whether you reason about multi-tape machines, single-tape machines, or an idealized random-access computer.

This robustness is captured in a working hypothesis called the Cobham-Edmonds thesis: a problem is feasibly (efficiently) solvable exactly when it is in P — solvable in polynomial time on a deterministic machine. It is the time-complexity cousin of the Church-Turing thesis you met earlier. Church-Turing said all reasonable models compute the SAME functions; Cobham-Edmonds adds that they do so within polynomial slowdown of each other, so the boundary 'polynomial vs not' lands in the same place no matter which reasonable model you pick. Note both are theses, not theorems — empirical bets about what 'reasonable' captures, not things you can prove from axioms.

It is this model-independence, not the literal accounting of tape moves, that earns P its central status. When a textbook says a problem is 'in P', it is making a claim that survives translation between machine models, programming languages, and most reasonable notions of a single computation step. That is why we can talk loosely about 'a polynomial-time algorithm' without first pinning down a machine — the class is stable enough that the details wash out.

The honest caveats: P is not quite 'feasible'

Now the honesty this rung owes you, because the slogan 'P equals feasible' is a useful idealization, not a law of nature. A polynomial with a monstrous constant or exponent can be useless in practice. An algorithm running in 10^100 times n steps, or in n^20, is technically in P, yet would never finish on any real input. The first known polynomial-time algorithm for a problem is often dreadfully impractical and only later refined; 'in P' is a statement about asymptotic GROWTH, and big-O deliberately hid the constants that decide whether you wait a second or a century. See guide 5 of this rung for the full reckoning.

It cuts the other way too: some problems with exponential WORST cases are solved fast every day in practice, and some genuinely useful methods are not even decision problems. P is a coarse, conservative line — a guarantee of good growth in the worst case, which is sometimes pessimistic and sometimes the wrong question entirely. So treat 'in P' as a strong sign a problem is approachable, not a certificate that any particular instance is quick, and never the reverse — that not being in P means useless.

Finally, a word to defuse a guaranteed confusion ahead. The next rung introduces NP, the class of problems whose proposed answers are easy to CHECK — like a jigsaw puzzle that is hard to finish but easy to verify once someone hands you the completed picture. A vital fact: P is a SUBSET of NP, written P is a subset of NP (if you can solve it quickly, you can certainly check a claimed solution quickly). And the famous question of whether P EQUALS NP — whether every easily-checkable problem is also easily-solvable — is OPEN. Nobody has proved it either way, and 'NP' does not mean 'not polynomial'. We will untangle all of that next; for now, just lodge the line: P is where deterministic, polynomial-time, always-halting decision lives.