The bargain we struck
By now you have met the central deal of complexity theory. We draw one line in the sand: an algorithm is good if its worst-case running time is bounded by some polynomial in the input size — n, n^2, n^3, n^100 — and bad if it needs exponential time like 2^n. Everything inside the line goes into the class P, the problems solvable in polynomial time on a deterministic machine. This is a genuinely powerful idea, and the rest of this guide is going to admire it honestly: praise where praise is due, and skepticism where it is earned.
Why is the polynomial-versus-exponential cut so seductive? Because of the ladder of growth rates you climbed in guide 2. Polynomials grow politely. Double the input and n^3 grows by a factor of 8 — annoying, survivable. Exponentials grow viciously: add just one symbol to the input and 2^n doubles. On a machine doing a billion steps a second, 2^n at n = 60 already outlasts the age of the universe. That gap is not a rounding error; it is the difference between a program and a fantasy.
Three reasons polynomial really is a good line
Before tearing the line down, let us see why so many sober people keep it. First, robustness. As guide 4 showed, P is the same class whether your machine is a one-tape Turing machine, a multi-tape one, or a random-access computer like the one on your desk. Translating between reasonable models costs only a polynomial blow-up, and a polynomial of a polynomial is still a polynomial. This is the spirit of the Cobham–Edmonds thesis: 'feasible' should mean polynomial precisely because that label does not wobble when you change hardware.
Second, closure. Polynomials are closed under addition, multiplication, and composition. So if you build a big algorithm by gluing together polynomial-time subroutines — call one inside a loop that itself runs a polynomial number of times — the whole thing is still polynomial. This is what lets us reason about programs the way we actually write them, as layers calling layers, without the cost exploding at every seam.
Third, it draws a real boundary in nature. The famous examples are not contrived. Sorting n numbers, finding a shortest path in a road network, deciding whether one city is reachable from another, even testing whether a number is prime — all live comfortably in P. Meanwhile a whole family of puzzle-like problems, the ones in NP, resist every polynomial-time algorithm anyone has found in fifty years. The line is doing honest work: it carves apart the problems we routinely crush from the ones that keep humbling us.
Where the comforting story leaks
Now the honesty. Equating 'in P' with 'feasible in practice' is a useful slogan, not a theorem, and it leaks in several places. The first leak is the hidden constants. Big-O throws away the multiplier out front. An algorithm that is O(n) but secretly does 10^40 * n steps is, on paper, a beautiful linear-time algorithm and, in your lifetime, completely useless. The limits of equating P with feasible start right here: polynomial says how the cost scales, not how big it is.
The second leak is the exponent. A polynomial with a huge exponent can be just as hopeless as an exponential, at every input size you will ever face. Some celebrated theoretical algorithms run in time like n^100 or worse; that is technically polynomial, technically 'in P', and technically unrunnable. For n = 100, n^100 is already 10^200 — there is no machine, and never will be, that does that many steps. So 'polynomial' alone is not a promise of speed.
Two more honest wrinkles: worst case and what 'feasible' even means
The third leak runs the other way. Our whole framework is built on worst-case analysis — we judge an algorithm by its slowest possible input. But the worst case can be a paranoid villain who never shows up. The simplex method for linear programming is exponential in the worst case, yet decades of real use make it one of the most reliable workhorses in computing, because the nasty inputs are vanishingly rare. So an algorithm can be 'not in P by our usual measure' and still be the right tool every single day. Honesty cuts both directions.
The fourth, deepest wrinkle is that 'feasible' is not a mathematical word at all. It depends on the year, the budget, the hardware, and how badly you need the answer. A computation that was infeasible on a 1980 mainframe is a phone app today. The class P is a precise, timeless mathematical object; 'feasible' is a moving human judgment. We borrow P as a stand-in for feasibility because it is stable and provable, but we should never forget we are translating a fuzzy idea into a sharp one and quietly hoping the seams hold.
growth at n = 50, machine does 1e9 steps/sec -------------------------------------------------- n^2 2,500 steps instant n^3 125,000 steps instant n^5 312,500,000 steps ~ 0.3 seconds n^100 ~ 1e170 steps > age of universe (still 'in P'!) 2^n ~ 1.1e15 steps ~ 13 days (NOT in P) n! ~ 3e64 steps > age of universe -------------------------------------------------- lesson: 'polynomial' and 'fast' are correlated, not identical.
Why we keep P anyway — and what comes next
Given all those leaks, why not throw P away? Because the alternatives are worse. A definition tied to 'runs in under a minute on my laptop' would change every year and differ between machines — it would not be a stable object you could prove theorems about. P trades a little real-world fidelity for enormous mathematical leverage: it is robust, it is closed under composition, and it gives us a fixed target so that proving a problem is not in P (or is as hard as the hardest problems in NP) becomes a sharp, meaningful claim.
Here is the right way to walk away from this rung. Read 'polynomial' as the floor of plausibility, not the ceiling of practicality. A problem in P is one we have a fighting chance with; a problem we can only solve in exponential time, like brute-forcing a jigsaw puzzle that is easy to check but hard to finish, is one where we expect to struggle. The slogan 'P means feasible' is a good first approximation that a serious person keeps gently quoted, never bare.
And notice the cliffhanger this leaves. We have a clean class of feasibly-solvable problems, and a stubborn crowd of puzzle-like problems that resist it. The natural next question is exactly the one the following rung opens: those puzzles are easy to check even when they seem hard to solve — what class captures that, how does it relate to P, and is the gap between them real or an illusion we just haven't seen through? That is the door marked NP, and the most famous open question in all of computer science is waiting right behind it.