P — polynomial time: Exercises — Coding deep dive

Prerequisite links you may want open while solving: Time complexity & Big-O, Turing Machine, TIME complexity classes, Cobham–Edmonds thesis, Polynomial-time reductions, NP — nondeterministic polynomial time.

Definition Notation used on this page (defined before use)

$n$ = the size of the input. Watch which meaning is active: sometimes $n$ is the number of bits needed to write the input down (the formal measure P uses), sometimes it is a problem parameter like "number of items in an array" or "number of vertices." Each exercise states which. When the two differ (as in primality), the whole game is converting one into the other.
$c$ , $k$ = unspecified positive constants that do not depend on $n$ . We write $c n^{k}$ to mean "at most some fixed multiple of $n^{k}$ ." Big-O notation $O (n^{k})$ hides exactly this $c$ ; see Time complexity & Big-O.
Fixed-degree polynomial = a bound $n^{k}$ where the exponent $k$ is a constant independent of $n$ (e.g. $n^{3}$ has $k = 3$ always). This is what keeps a problem in P; if the exponent itself grew with $n$ , you would have left P.
$TIME (T (n))$ = the class of decision problems a deterministic Turing machine can decide in at most $O (T (n))$ steps. Then $P = ⋃_{k \geq 1} TIME (n^{k})$ — "polynomial time for some fixed $k$ ." See TIME complexity classes.
For graphs: $V$ = the number of vertices, $E$ = the number of edges.
$(2 V)$ = " $V$ choose 2" = the number of ways to pick an unordered pair of vertices out of $V$ . Since a simple graph has at most one edge per pair, $(2 V)$ is the maximum possible number of edges. Its formula is $(2 V) = \frac{V ( V - 1 )}{2}$ (each of the $V$ vertices can pair with the other $V - 1$ , and dividing by $2$ removes the double-count of "pair $uv$ " = "pair $v u$ "). More generally $(3 V)$ counts unordered triples of vertices, $(3 V) = \frac{V ( V - 1 ) ( V - 2 )}{6}$ .

Level 1 — Recognition

(Can you read the definition and apply it directly?)

Exercise 1.1 — Is it a decision problem?

Classify each as a decision problem (yes/no) or not: (a) "Is $N$ prime?" (b) "Sort this list." (c) "Does graph $G$ have a path from $s$ to $t$ ?" (d) "How many edges does $G$ have?"

Recall Solution 1.1

A decision problem asks a yes/no question — formally, "is the input in language $L$ ?"

(a) Yes/no ✅ decision problem ( $x \in PRIMES$ ?).
(b) Not a decision problem — it outputs a rearranged list, not yes/no. (Its decision version would be "is this list already sorted?")
(c) Yes/no ✅ decision problem (reachability).
(d) Not — it outputs a number, not yes/no. (Decision version: "does $G$ have $\geq B$ edges?")

Exercise 1.2 — Read the growth table

Using the parent note's table, at the parameter value $n = 50$ (here $n$ is the plain problem parameter, the number $50$ , not a bit-length) which is larger, $n^{3}$ or $2^{n}$ ? By roughly what factor?

Recall Solution 1.2

$n^{3} = 5 0^{3} = 125, 000$ . $2^{50} \approx 1.13 \times 1 0^{15}$ . $2^{n}$ is larger by a factor of about $\frac{2 ^{50}}{5 0 ^{3}} \approx \frac{1.13 \times 1 0 ^{15}}{1.25 \times 1 0 ^{5}} \approx 9.0 \times 1 0^{9},$ roughly 9 billion times larger. The exponential has already run away. (This growth gap is drawn in the figure under Level 2.)

Exercise 1.3 — Which are in P?

Which of these are known to be in P? (a) $s$ – $t$ reachability (b) Multiplying two $n$ -digit numbers (c) Deciding whether $N$ is prime (d) Sorting $n$ numbers.

Recall Solution 1.3

First reframe the non-decision ones. P is a class of decision languages only, so (b) and (d) — which produce outputs, not yes/no — must be converted to yes/no versions before we can even ask "is it in P?" (their function versions live in FP, a separate class):

(b) Multiplication → the decision language ${(x, y, z) : x \cdot y = z}$ ("is $z$ the product of $x$ and $y$ ?").
(d) Sorting → the decision language ${L : L is a list already in non-decreasing order}$ ("is this list sorted?"). (An equivalent useful version: "does the sorted list have element $\leq B$ in position $i$ ?")

Now judging membership, all four decision problems are in P:

(a) reachability: BFS in $O (V + E)$ where $V, E$ are the vertex and edge counts. ✅
(b) " $x \cdot y = z$ ?": compute the product by schoolbook multiplication in $O (m^{2})$ (with $m$ = number of digits), then compare to $z$ in $O (m)$ . ✅
(c) " $N$ prime?": AKS, polynomial in $n = lo g N$ bits. ✅
(d) "sorted?": one left-to-right scan comparing adjacent items, $O (m)$ for $m$ items. ✅

Membership in P only needs one polynomial algorithm to exist — not the fastest.

Level 2 — Application

(Count steps and bound them. Here $n$ = number of items in the array.)

Exercise 2.1 — Bound a nested loop

An algorithm on an array of $n$ items runs two nested loops, the inner doing $O (1)$ work per pair. Give the step count and state whether it is in P.

Recall Solution 2.1

Let $c$ be some fixed positive constant (the work per inner iteration, independent of $n$ ). Outer loop $n$ times, inner loop $n$ times: $steps = c \cdot n \cdot n = c n^{2} = O (n^{2}) .$ $n^{2}$ is a polynomial in input size $n$ (the array has $n$ items). ✅ In P.

Exercise 2.2 — Three nested loops

Same setup but three nested loops, each running $n$ times. Step count? Still in P?

Recall Solution 2.2

With $c$ again a fixed positive constant independent of $n$ : $steps = c n \cdot n \cdot n = c n^{3} = O (n^{3}) .$ This is a polynomial $n^{k}$ with $k = 3$ — a constant exponent, independent of $n$ — so it stays in P. ✅ The figure below shows why three loops is still fine: read the vertical axis (steps) against the horizontal axis (input size $n$ ). The green curve $n^{3}$ and blue curve $n^{2}$ both stay near the floor, while the red curve $2^{n}$ shoots off the top of the chart near $n = 20$ . The lesson to observe: a fixed power of $n$ grows slowly compared to $2^{n}$ , no matter how many loops (as long as their count is a constant).

Exercise 2.3 — Reachability on a specific graph

A graph has $V = 6$ vertices and $E = 9$ edges (recall $V$ = vertex count, $E$ = edge count). Give an upper bound on BFS steps, and check it against the polynomial bound $n^{2}$ (with $n = V$ ).

Recall Solution 2.3

BFS visits each vertex once and inspects each edge a constant number of times, so its cost is at most $c (V + E)$ for some fixed constant $c$ . Here $V + E = 6 + 9 = 15$ , so BFS uses at most $c \cdot 15$ steps. The parent bound (treating $n = V$ ): a simple graph has at most $(2 V) = \frac{V ( V - 1 )}{2}$ edges (see the notation box), so $V + E \leq V + (2 V) = 6 + \frac{6 \cdot 5}{2} = 6 + 15 = 21 \leq V^{2} = 36. ✅$ So the exact work $V + E = 15$ is bounded by the polynomial $n^{2} = 36$ — comfortably polynomial.

Level 3 — Analysis

(Spot why a bound is or isn't polynomial in the right variable.)

Exercise 3.1 — The primality trap

Trial division tests divisors up to $N$ . For $N$ with $n = ⌈ lo g_{2} N ⌉$ bits (here $n$ is the bit-length, the formal input size), express the step count in terms of $n$ and explain why this does not prove $PRIMES \in P$ .

Recall Solution 3.1

Steps $\approx N = N^{1/2}$ . Since $N \leq 2^{n}$ , $N = 2^{n /2} .$ That is exponential in $n$ , the true input size (bits). A polynomial bound must look like $c n^{k}$ with $k$ a constant; $2^{n /2}$ is not of that form (the exponent grows with $n$ ). So trial division is not a P proof. PRIMES is in P — but via the AKS algorithm, which runs in $poly (n)$ .

Exercise 3.2 — Numeric feel for the trap

Take $N = 2^{40}$ (so $n = 40$ bits). Compare trial-division steps ( $N$ ) against a hypothetical $n^{3}$ algorithm.

Recall Solution 3.2

Trial division: $N = 2^{20} = 1, 048, 576 \approx 1 0^{6}$ steps. $n^{3} = 4 0^{3} = 64, 000$ steps. Ratio $\approx 1, 048, 576/64, 000 \approx 16.4$ — trial division already does ~16× more work at a tiny 40-bit input, and the gap explodes as $n$ grows.

Exercise 3.3 — Is $n^{100}$ in P?

Is an algorithm running in $c n^{100}$ steps (with $c$ a fixed positive constant) in P? Is it "practical"? Reconcile.

Recall Solution 3.3

Yes, it is in P: $n^{100}$ is a polynomial with exponent $k = 100$ — a constant independent of $n$ — so it lies inside $TIME (n^{100})$ , and hence inside $P = ⋃_{k \geq 1} TIME (n^{k})$ . (Recall $TIME (T (n))$ = problems decidable by a deterministic TM in $O (T (n))$ steps.) Practical? No — even $n = 10$ gives $1 0^{100}$ steps, more than atoms in the universe. Reconcile: P is a theoretical boundary of feasibility, not a promise of speed. It survives as a useful notion because real-world poly algorithms tend to have small exponents (2, 3, occasionally higher). "In P" ≠ "quick," it means "in-principle tractable."

Level 4 — Synthesis

(Combine algorithms; use closure properties.)

Exercise 4.1 — Composing two poly algorithms

Subroutine $A$ runs in $O (n^{2})$ . Algorithm $B$ calls $A$ once for each of $n$ items, plus $O (n^{3})$ extra work. Total time? Still polynomial?

Recall Solution 4.1

$A$ is called $n$ times: $n \cdot O (n^{2}) = O (n^{3})$ . Add the extra $O (n^{3})$ : $O (n^{3}) + O (n^{3}) = O (n^{3}) .$ ✅ Polynomial. This is the closure under composition argument from the parent: poly number of calls to a poly subroutine, plus poly glue, stays poly.

Exercise 4.2 — Poly of a poly

Algorithm $C$ produces an output of length $m = O (n^{2})$ , then feeds it to $A$ (which runs in $O (m^{2})$ ). Total time in terms of $n$ ?

Recall Solution 4.2

$A$ on input of length $m$ costs $O (m^{2})$ . Substitute $m = O (n^{2})$ : $O ((n^{2})^{2}) = O (n^{4}) .$ Add $C$ 's own cost (say $O (n^{2})$ ) → still $O (n^{4})$ . ✅ Polynomial. This uses $(n^{a})^{b} = n^{ab}$ : a polynomial of a polynomial is a polynomial. That closure is exactly why P is chosen as the feasibility class.

Exercise 4.3 — Closure under complement

$A \in P$ via decider $M$ running in $O (n^{k})$ . Show $\overline{A} \in P$ and give its bound.

Recall Solution 4.3

Build $M^{'}$ : run $M$ on $x$ (cost $O (n^{k})$ ), then flip its answer (yes↔no) in $O (1)$ . $M^{'}$ decides $\overline{A}$ correctly and runs in $O (n^{k}) + O (1) = O (n^{k})$ . ✅ $\overline{A} \in P$ , same polynomial degree. This is why P is closed under complement — see Polynomial-time reductions for the general composition machinery.

Level 5 — Mastery

(Prove a subtle membership; reason about model-robustness.)

Exercise 5.1 — Same number, different encoding

Consider deciding "is $N$ even?" when $N$ is given (a) in binary ( $n = lo g_{2} N$ bits) versus (b) in unary (a string of $N$ ones, length $N$ ). Is the problem in P under each encoding? What does this teach?

Recall Solution 5.1

(a) Binary: just read the last bit — $O (1)$ , or $O (n)$ to scan the string. Polynomial in $n = lo g_{2} N$ . ✅ In P. (b) Unary: the input length is $N$ itself, so scanning it is $O (N)$ — but $N$ is the input size here, so $O (N)$ is linear in the input length, hence polynomial in that size. ✅ Also in P (under the unary measure). Lesson: "in P" is always relative to the encoding length. A problem can flip between exponential-looking and polynomial purely by changing the encoding (this is exactly the primality trap — value vs bits). Reasonable encodings are within polynomial factors of each other; pathological ones like unary are not, so we standardise on binary. See Cobham–Edmonds thesis.

Exercise 5.2 — Model robustness

A single-tape TM simulating a $k$ -tape TM incurs at most a quadratic slowdown. If the $k$ -tape machine runs in $O (n^{3})$ , bound the single-tape running time and conclude membership in P is unchanged.

Recall Solution 5.2

Step 1 — WHAT the slowdown theorem says (state the bound). A standard TM result: any computation that a $k$ -tape machine performs in $t$ steps can be reproduced by a single-tape machine in at most $O (t^{2})$ steps. Why quadratic: to mimic one step of the multitape machine, the single-tape machine sweeps across its whole tape to find and update the $k$ simulated head positions; after $t$ steps the used tape has length $O (t)$ , and each of the $t$ simulated steps costs an $O (t)$ sweep, giving $t \cdot O (t) = O (t^{2})$ . Step 2 — WHY this settles P. Plug in the given $k$ -tape runtime $t = O (n^{3})$ : $O (t^{2}) = O ((n^{3})^{2}) = O (n^{6}) .$ This is still a polynomial with a constant exponent ( $k = 6$ ), so the language, decidable in $O (n^{6})$ on a single-tape machine, is in $P$ — the same class it was in on the $k$ -tape machine. Step 3 — WHY that means P is model-robust. The exponent merely doubled ( $3 \to 6$ ); a polynomial squared is still a polynomial ( $(n^{a})^{2} = n^{2 a}$ , closure from Exercise 4.2). So switching machine models can only multiply the exponent by a constant — it can never turn polynomial into exponential. That is precisely why "is it in P?" gives the same answer on a single-tape TM, a $k$ -tape TM, a RAM, or your laptop. This model-independence is the content of the Cobham–Edmonds thesis; see Cobham–Edmonds thesis and Turing Machine.

Exercise 5.3 — Prove a membership from scratch

Prove that $L = {G : G is a graph with a triangle}$ is in P. State the algorithm, count steps in the input size, and give the polynomial bound. (Here $V$ = number of vertices, $E$ = number of edges.)

Recall Solution 5.3

Encoding: represent $G$ by its adjacency matrix, a $V \times V$ table of size $Θ (V^{2})$ bits, so that testing whether any single edge $uv$ exists is an $O (1)$ table lookup. Algorithm: for every unordered triple of vertices ${u, v, w}$ , check whether all three edges $uv, v w, u w$ are present. Accept iff some triple is a triangle. Step count: number of triples $= (3 V) = \frac{V ( V - 1 ) ( V - 2 )}{6} = O (V^{3})$ (see the notation box for $(3 V)$ ); each triple checks $3$ edges in $O (1)$ (adjacency matrix). Total: $O (V^{3}) .$ Input size: with the adjacency-matrix representation the input is $n = Θ (V^{2})$ bits, so $V = Θ (n)$ , giving $O (V^{3}) = O (n^{3/2}),$ a polynomial with constant exponent $3/2$ . ✅ Either way — in $V$ or in bit-length $n$ — the bound is a fixed-degree polynomial, so $L \in P$ .

Common mistake L5 trap — "polynomial in

$V$ but forgot the encoding" Why it feels right: you correctly get $O (V^{3})$ and call it done. The truth: the formal definition of P counts steps against the bit-length $n$ of the encoded input, not against $V$ . Here it happens to still be polynomial ( $O (n^{3/2})$ ), but for a problem where $V$ is given as a single number (like "complete graph on $V$ vertices" with $V$ in binary), $O (V^{3}) = O (2^{3 n})$ would be exponential in $n$ . Fix: always finish by converting your bound into the input's bit-length, then judge polynomial vs exponential. Picture the fix: an adjacency matrix of $V$ vertices spreads the input over $Θ (V^{2})$ cells (long paper strip → $V = Θ (n)$ ), but a single binary number $V$ packs it into $n = lo g_{2} V$ symbols (short strip → $V = 2^{n}$ ). Same $V$ , wildly different strip length — and the strip length is what P measures against.

Wrap-up recall

Connections

4.6.22 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