P — polynomial time: Visual walkthrough — Coding deep dive

Parent: P — polynomial time · this page rebuilds the central claim — "a problem is in P when we can bound its step-count by a polynomial in the input's length" — from absolute zero, one picture at a time.

We are going to prove, in slow motion, why the same problem (deciding whether a number is prime) can look "easy" and yet fail to be a proof that it lives in P — and what a real P-proof looks like. Along the way every word (input, length, step, polynomial, exponential) gets earned before it is used.

Step 1 — What is an "input", and what is its size?

WHAT. A computer never sees a "number" or a "graph" directly. It sees a string of symbols you typed to describe it — a row of boxes, each holding one character (a $0$ or a $1$ , say). The input is that row of boxes.

WHY. Everything we measure — time, memory — will be measured against how big this row is, so we must pin down "big" precisely before doing anything else. We call the number of boxes the input length and write it $n$ .

PICTURE. Below, the same idea (the number "thirteen") is written two ways. On top it is one lonely symbol; underneath it is the row of bits a machine actually stores. Count the boxes — that is $n$ .

Notation earned so far: $x$ = the input string, $n = ∣ x ∣$ = how many boxes it fills.

Step 2 — What is a "step", and what is "time"?

WHAT. A Turing Machine does exactly one tiny thing per tick: read the box under its head, maybe write a symbol, move one box left or right. Each tick is one step. The running time is just how many ticks pass before the machine stops and answers.

Throughout this page the machine is deterministic: from each configuration there is exactly one next move (no guessing, no branching). This matters because the class P is defined precisely as deterministic polynomial time — the guessing version lives in NP — nondeterministic polynomial time, a different club.

WHY. We want a count that does not depend on your particular laptop's clock speed — a machine-independent tally. Counting steps (not seconds) does that. Two boxes moved = two steps, whether your CPU is fast or slow.

PICTURE. Watch the head crawl across the tape. Each red hop is one step; the counter on the right ticks up.

Step 3 — Two families of growth: polynomial vs exponential

WHAT. We compare two shapes a step-count can take as $n$ grows:

polynomial: $n^{k}$ — like $n^{2}$ , $n^{3}$ . Symbol $k$ is a fixed whole number, the exponent, decided once and never changing.
exponential: $2^{n}$ — here $n$ is up in the exponent, so it drives the growth.

WHY this comparison and not another? Because the whole point of complexity theory is separating "the work grows steadily" from "the work explodes". Polynomials grow steadily; putting $n$ in the exponent makes the count double for every extra box. That doubling is the wall we want to detect.

PICTURE. The lavender curve $n^{2}$ and the coral curve $2^{n}$ start close, then the coral one shoots off the top of the chart. Notice where they cross — after that, exponential is hopeless forever.

Term by term: $c$ is a fixed multiplier (hardware slack), $n^{k}$ is the polynomial ceiling, $\leq$ says "never worse than this".

Step 3½ — A word we're about to lean on: Big-O

WHAT. Before Step 4 we need one shorthand. When we write $O (f (n))$ — read "big-O of $f$ of $n$ " — we mean: "grows no faster than $f (n)$ , once you allow a constant multiplier and ignore small inputs."

WHY this tool and not exact counts? Because the exact step-count depends on fussy details (which tape model, how you break ties) that we deliberately don't care about — remember from Step 2 we only want a machine-robust shape of growth. Big-O throws away the constant $c$ and the low-order clutter and keeps only the shape.

So " $O (V)$ work" just means "at most (some constant) $\times V$ steps"; the constant is swept under the rug on purpose. See Time complexity & Big-O for more.

Step 4 — Worked case that works: is there an $s$ – $t$ path? (in P)

WHAT. Given a graph, ask: can I walk from vertex $s$ to vertex $t$ ? We run Breadth-First Search — flood outward from $s$ one ring at a time and see if the flood reaches $t$ .

First, two names we will count with:

$V = ∣ vertices ∣$ = the number of dots in the graph;
$E = ∣ edges ∣$ = the number of lines connecting dots.

WHY BFS and why count this way? Because we don't guess membership in P — we count steps and bound them (now using the Big-O shorthand from Step 3½). BFS touches each vertex once and each edge a constant number of times, so its count is easy to bound.

PICTURE. The flood spreads in coloured rings. Every vertex lights up once (mint), every edge is crossed at most twice (coral). Tally them.

Why $n \geq V$ — spelling out the encoding. We must pin down how the graph is written down before we can compare $n$ to $V$ . Writing a graph on $V$ vertices means naming vertices, and each distinct name needs $⌈ lo g_{2} V ⌉$ bits to distinguish it from the others.

Adjacency-matrix encoding: you write a $V \times V$ grid of $0/1$ entries (entry $= 1$ if an edge exists), so the string is exactly $V^{2}$ symbols → $n = V^{2} \geq V$ .
Adjacency-list encoding: you list, for each vertex, its neighbours' labels; each of the $V$ vertices contributes at least its own $⌈ lo g_{2} V ⌉$ -bit label, so $n \geq V ⌈ lo g_{2} V ⌉ \geq V$ .

Under either reasonable encoding, $n \geq V$ . And since a graph on $V$ vertices has at most $(2 V) < V^{2}$ edges, we get $V + E < V + V^{2} \leq n + n^{2} = O (n^{2})$ . (Even the extra $lo g V$ -bit label handling per step only multiplies the count by a further $O (lo g V) = O (n)$ factor, which is still polynomial.) So BFS runs in $O (n^{2})$ steps (poly even with bit-level bookkeeping) — a polynomial in $n$ . ✅ Reachability $\in$ P.

Step 5 — The trap case: is $N$ prime by trial division? (looks fast, isn't)

WHAT. Here the input string $x$ is the ==binary encoding of an integer $N$ == — so $x$ is a row of $n = ∣ x ∣ = ⌈ lo g_{2} N ⌉$ bits (exactly the "value vs length" split from Step 1, with $N$ the value and $n$ the length). To test if $N$ is prime, try dividing $N$ by every candidate up to $N$ . That's about $N$ divisions. Small number of operations... right?

WHY it's a trap — reason one (the value/length gap). Remember Step 1: time is measured against length $n$ , not the value $N$ . Since $N \leq 2^{n}$ , we have: $N = N^{1/2} \leq (2^{n})^{1/2} = 2^{n /2},$ and for $N$ near the top of its bit-range this is $\approx 2^{n /2}$ . The number of divisions is already $\approx 2^{n /2}$ — exponential in $n$ ! It only looked small because we compared it to the giant value $N$ instead of the tiny length $n$ .

WHY it's a trap — reason two (each division isn't free). On a deterministic Turing Machine, dividing two $n$ -bit numbers is not one step — it costs $poly (n)$ bit-operations (schoolbook long division is $O (n^{2})$ bit-steps). So the honest total is $T (n) \approx number of divisions 2^{n /2} \times bit-cost of one division O (n^{2}) = O (n^{2} 2^{n /2}),$ which is even worse — still dominated by the exponential $2^{n /2}$ . Adding the true bit-cost only makes trial division more clearly non-polynomial.

PICTURE. The horror in one frame: the input box is short (few bits), but the work bar next to it towers, because it scales with $2^{n /2}$ , not with $n$ .

Step 6 — The real proof: PRIMES ∈ P via a genuinely poly-in- $n$ method

WHAT. Being in P never depends on your first algorithm — only on whether some deterministic algorithm has a polynomial step-count in $n$ . For primality (input $=$ the $n$ -bit encoding of $N$ ), the AKS algorithm (2002) runs in time polynomial in $n = lo g N$ , counting real bit-operations.

How poly, concretely? AKS is not just "poly" hand-waved — it has an explicit exponent. The original bound is $O (n^{12})$ (up to logarithmic factors) bit-operations; later refinements push it to about $O (n^{6})$ . Either way the exponent is a fixed constant — that is exactly the " $n^{k}$ with $k$ fixed" shape from Step 3, so it is genuinely in P.

WHY this fixes Step 5. Step 5's honest count was $\approx n^{2} 2^{n /2}$ (off the chart because of the exponential factor). AKS's count is a tame $n^{k}$ with $k = 12$ (or $6$ ) — big exponent, but fixed. Same problem, different algorithm — and one polynomial algorithm is all P ever requires.

PICTURE. Both attempts on one axis measured correctly against $n$ : trial division's coral exponential wall vs AKS's lavender polynomial curve hugging the floor.

Step 7 — Why "polynomial" is the right fence (closure)

WHAT. Suppose subroutine $A$ runs in $n^{a}$ steps and you call it inside algorithm $B$ that itself does $n^{b}$ rounds. Total work multiplies: $rounds of B n^{b} \times cost of each A n^{a} = n^{a + b} .$

WHY this seals the deal. $n^{a + b}$ is still a polynomial — a fixed exponent. Poly-inside-poly stays poly. This closure is why P is stable: combine efficient pieces, stay efficient. Exponential time has no such clean rule, which is the real reason the fence is drawn at "polynomial" (this is the spirit of the Cobham–Edmonds thesis, and it's what makes P robust across every deterministic model — see TIME complexity classes).

PICTURE. Poly boxes nesting inside poly boxes — and the outermost box is still just a polynomial box.

The one-picture summary

One decision axis: convert every algorithm's step-count into a function of the length $n$ (counting real bit-operations), then read off which side of the polynomial/exponential fence it lands on. Reachability and AKS land in P; trial division, measured honestly, does not.

Recall Feynman: the whole walk in plain words

First we agreed a puzzle is really just the row of letters you typed to describe it, and its "size" $n$ is how many letters that is (Step 1). A "step" is one tick of a tiny deterministic machine — one that never guesses — and "time" is how many ticks (Step 2). Then we drew two growth shapes: steady $n^{2}$ and explosive $2^{n}$ — the only difference is whether $n$ sits in the base or up in the exponent (Step 3). We introduced Big-O as a way to say "no faster than this shape, ignoring the constant" (Step 3½). We proved graph-walking is steady by counting: each dot ( $V$ ) once, each line ( $E$ ) twice (Step 4). Then the sneaky bit: the input is the binary encoding of a number $N$ , written in only $n = lo g_{2} N$ boxes, so trying divisors up to $N$ is really $2^{n /2}$ divisions — and each division itself costs poly-many bit-steps — an explosion in disguise (Step 5). The honest fix is a cleverer method (AKS, about $n^{12}$ bit-operations) that really is steady in $n$ (Step 6). And the reason "steady = polynomial" is the right rule: steady-inside-steady is still steady, so you can build big efficient programs out of small ones (Step 7). Motto: bits, not value.

Convert

N

into a function of bit-length

n = lo g_{2} N

N \approx 2^{n /2}

, exponential in

n

(and each division adds a poly-

n

bit-cost on top).

What does

O (f (n))

mean formally?

There are constants

c > 0, n_{0}

with

T (n) \leq c f (n)

for all

n \geq n_{0}

— "no faster than

f

, ignoring the constant and small inputs".

Why is P closed under composing poly algorithms?

n^{a}

inside

n^{b}

gives

n^{a + b}

, still a fixed-exponent polynomial.

What is the membership rule for P?

Exhibit one deterministic machine whose step-count, expressed in

n

(counting real bit-operations), is bounded by some

c n^{k}

Connections

Parent: P — polynomial time
NP — nondeterministic polynomial time
P vs NP problem
Polynomial-time reductions
NP-complete problems
Time complexity & Big-O
Turing Machine
Cobham–Edmonds thesis
TIME complexity classes