--- title: 'Class P' source: 'https://academia.sh/en/courses/theory-of-computation/class-p' course: 'Theory of Computation' language: en updated: '2026-08-17T18:08:28+00:00' license: 'CC BY-SA 4.0' --- # Class P Measuring decision problems solvable in polynomial time under a finite step budget: on the same 20 examples, the threshold problem is decided in 12 steps, the pair problem in 66, while subset sum requires a budget of 10,000 steps. As input size rises from 8 to 20, the first two methods' worst-case steps go from 8 to 20 and from 28 to 190, while the third rises from 256 to 1,048,576. The difference between the decision problem class and the growth class from the Algorithms course is stated separately. The Models of Computation topic asked whether a question can be answered at all, and measured that a finite budget cannot always close that question. The Complexity Classes topic works in a narrower field: among problems whose answer **can** be found, it asks how the cost of finding it grows with the input. The first question is this: what makes a problem cheap, and is cheapness a property of the problem or of the chosen method. This lesson runs three decision problems on the same input with the same budget. Two of them barely strain the budget; the third requires the budget to grow. What is measured is not which one is "fast," but **which one the budget decides**. - **CC1.** Every problem in this topic is a **decision problem**: the answer is a single word, "yes" or "no." The concept of a decision problem was established in the Advanced Algorithms course and is not repeated here. - **CC2.** Input size **n** is the number of values in an example. The values are kept between 3 and 99, so a value's digit count is fixed, and input size varies only with n. - **CC3.** The measure is **steps**, not time. What a step is is defined separately for each method, and that definition does not change over the course of the lesson. - **CC4.** The **budget** is a step budget. If a method exhausts the budget, it gives no answer; it returns "undecided." This does not mean there is no answer — it means one **could not be established within this budget**. - **CC5.** Examples come from the shared definition's generator: seed **20260218**, 20 examples, **12 numbers** per example. This course has **no second seed**; instead it has budget sweeps. - **CC6.** The three problems: **Threshold** — does the sum of the numbers exceed the target. **Pair** — do two numbers sum exactly to the target. **Subset sum** — does some subset sum exactly to the target. - **CC7.** A **budget sweep is mandatory.** Every result is shown at at least three budget values, and whether it changes with the budget is stated. - **CC8.** A method's **observed** steps and its **worst-case** steps are written separately. Conflating the two erases the difference this lesson measures. - **CC9.** Whether a problem belongs to class P is **not measured**. The only thing measured is how a specific method's step count grows with input size. - **CC10.** Constant factors are **not dropped**. The measure is not asymptotic; it is the counted step. ## The Decision Problem Class and the Growth Class The Algorithms course's lesson "Reading Complexity Classes" also used the term "complexity class," but it named a different thing. The difference fits in one sentence: there, a class groups a single method's cost expression — $O(n^2)$ is the growth shape of two nested loops — here, a class groups **problems** for which a method is being sought. The distinction's practical consequence is this. A method always belongs to a growth class; this is determined by looking at the code. A **problem**, on the other hand, can only be placed into a decision problem class by showing that "such a method exists," and this is an **existence claim**. Code is measured; an existence claim is not. **P** is a decision problem class: problems for which there exists a deterministic method that gives an **exact** answer in a number of steps bounded by a polynomial in the input size. All three words in the definition carry weight. "Polynomial" is a growth bound; "exact" excludes approximate solutions; "exists" is an existence claim and cannot be established by a single run. ## Three Decision Problems, One Step Budget The block below runs the three problems on the same 20 examples. Each method takes a step budget and, once the budget is exhausted, returns `None` to signal it could not decide. ```python SEED = 20260218 def examples(seed=SEED, n=12, count=20): """Shared definition's example generator: each example is n numbers and a target.""" d = seed result = [] for _ in range(count): numbers = [] for _ in range(n): d = (d * 1103515245 + 12345) % 2147483648 numbers.append(d % 97 + 3) d = (d * 1103515245 + 12345) % 2147483648 result.append({"numbers": numbers, "target": sum(numbers) // 3 + d % 7}) return result def threshold(numbers, target, budget): """Does the sum exceed the target. One step = one addition.""" total, steps = 0, 0 for s in numbers: if steps >= budget: return None, steps total += s steps += 1 return total > target, steps def pair(numbers, target, budget): """Do two numbers sum to the target. One step = one pair.""" steps, n = 0, len(numbers) for i in range(n): for j in range(i + 1, n): if steps >= budget: return None, steps steps += 1 if numbers[i] + numbers[j] == target: return True, steps return False, steps def subset_sum(numbers, target, budget): """Does some subset sum to the target. One step = one subset.""" steps, n = 0, len(numbers) for mask in range(1 << n): if steps >= budget: return None, steps steps += 1 if sum(numbers[i] for i in range(n) if mask >> i & 1) == target: return True, steps return False, steps EX = examples() print("budget method decided undecided most steps") for b in (12, 100, 1000, 10000): for name, f in (("threshold ", threshold), ("pair ", pair), ("subset sum", subset_sum)): answered = highest = 0 for o in EX: y, a = f(o["numbers"], o["target"], b) if y is not None: answered += 1 highest = max(highest, a) print(f"{b:5d} {name} {answered:15d} {20 - answered:11d} {highest:11d}") ``` ``` budget method decided undecided most steps 12 threshold 20 0 12 12 pair 0 20 0 12 subset sum 0 20 0 100 threshold 20 0 12 100 pair 20 0 66 100 subset sum 7 13 98 1000 threshold 20 0 12 1000 pair 20 0 66 1000 subset sum 19 1 354 10000 threshold 20 0 12 10000 pair 20 0 66 10000 subset sum 20 0 1047 ``` ## What the Budget Answers, What It Cannot Three numbers stand side by side. **Budget 12**: the threshold problem decides 20 of 20 examples, the other two problems decide **none**. **Budget 100**: the pair problem also reaches 20 of 20 and spends at most 66 steps; subset sum stays at **7 examples**, 13 remain undecided. **Budget 10,000**: all three reach 20 of 20. Reading the budget sweep gives two separate results here. For the threshold and pair problems, raising the budget from 100 to 10,000 **changes nothing**: the maximum steps stay fixed at 12 and 66, because these two methods have already exhausted the input. For subset sum, raising the budget **changes everything**: 7, then 19, then 20. This course's second claim shows up twice in a single table. The meaning of the numbers that stay fixed matters more than the ones that don't. The threshold method's 12 steps come from there being 12 numbers in the input; the pair method's 66 steps come from 12 numbers having 66 pairs. Both are numbers readable from the input itself and can be written down beforehand without looking at the example. Subset sum's steps of 98, 354, and 1047, by contrast, cannot be written beforehand; which mask it stops on depends on the example. ## As Input Size Grows A result taken at one budget value may not hold up when input size changes. The second sweep raises input size from 8 to 20 and places each method's worst-case step count next to the highest observed step count. ```python SEED = 20260218 def examples(seed=SEED, n=12, count=20): d = seed result = [] for _ in range(count): numbers = [] for _ in range(n): d = (d * 1103515245 + 12345) % 2147483648 numbers.append(d % 97 + 3) d = (d * 1103515245 + 12345) % 2147483648 result.append({"numbers": numbers, "target": sum(numbers) // 3 + d % 7}) return result def subset_sum_first(numbers, target): """All subsets; stops at the first match. One step = one subset.""" steps, n = 0, len(numbers) for mask in range(1 << n): steps += 1 if sum(numbers[i] for i in range(n) if mask >> i & 1) == target: return True, steps return False, steps print(" n threshold pair subset sum (worst case) subset sum (observed max)") for n in (8, 12, 16, 20): highest = max(subset_sum_first(o["numbers"], o["target"])[1] for o in examples(n=n)) print(f"{n:2d} {n:9d} {n * (n - 1) // 2:5d} {1 << n:23d} {highest:26d}") ``` ``` n threshold pair subset sum (worst case) subset sum (observed max) 8 8 28 256 256 12 12 66 4096 1047 16 16 120 65536 945 20 20 190 1048576 2684 ``` The threshold column is 8, 12, 16, 20 — one-to-one with input size. The pair column is 28, 66, 120, 190; as input size rises two and a half times, steps rise roughly sevenfold, that is, **quadratic growth**. The subset column's worst case goes from 256 to **1,048,576**: every new number doubles the count of subsets to be scanned. The last column exposes a trap. The highest **observed** step count is 1047 at 12 numbers, 945 at 16, 2684 at 20. That is, the observed value does not rise steadily with input size — it even drops going from 12 to 16. The reason is that the method stops at the first matching subset; in these examples, a matching subset happens to be found early. In the row for eight numbers, the observed value **coincides** with the worst case — 256 against 256 — because that batch contains an example where no subset matches at all, and there the scan runs to the very end. The rule that follows is this: **an observed step count is not a method's cost.** The highest observed value being 2684 over twenty examples does not say the twenty-first example will finish in 2684 steps. Writing down a method's cost means writing a bound that holds for **every** input, not an observed number. ## What Input Size Is Measured In The "polynomial" in the definition of P is a polynomial **of input size**. What input size actually is is therefore part of the definition, and carelessness at this point turns into a silent error. For subset sum there is another method besides exhaustive search: a table of reachable sums is kept, and every number updates the table once. This method spends **n times target** steps, that is, about 2160 steps for 12 numbers and a target of 180 — below 4096. On the face of it, this is a polynomial method. The block below tests this appearance. All numbers and the target are scaled by the same factor; **the count of numbers stays the same**, only each number's digit count grows. ```python SEED = 20260218 def examples(seed=SEED, n=12, count=20): d = seed result = [] for _ in range(count): numbers = [] for _ in range(n): d = (d * 1103515245 + 12345) % 2147483648 numbers.append(d % 97 + 3) d = (d * 1103515245 + 12345) % 2147483648 result.append({"numbers": numbers, "target": sum(numbers) // 3 + d % 7}) return result def brute_force(numbers, target): """One step = one subset.""" steps, n = 0, len(numbers) for mask in range(1 << n): steps += 1 if sum(numbers[i] for i in range(n) if mask >> i & 1) == target: return True, steps return False, steps def dp(numbers, target): """Reachable-sum table. One step = one table cell.""" reached = [False] * (target + 1) reached[0] = True steps = 0 for s in numbers: for t in range(target, s - 1, -1): steps += 1 if reached[t - s]: reached[t] = True return reached[target], steps print("factor digits agree brute-force steps dp steps") for c in (1, 10, 100): agree, bfs, dps = 0, 0, 0 digits = 0 for o in examples(): s = [x * c for x in o["numbers"]] h = o["target"] * c digits = max(digits, len(str(h))) y1, a1 = brute_force(s, h) y2, a2 = dp(s, h) agree += y1 == y2 bfs, dps = bfs + a1, dps + a2 print(f"{c:6d} {digits:6d} {agree:5d} {bfs:17d} {dps:9d}") ``` ``` factor digits agree brute-force steps dp steps 1 3 20 4321 37994 10 4 20 4321 377780 100 5 20 4321 3775640 ``` The two methods give the same answer on all 20 examples, so the table method works correctly. But the step columns move in opposite directions. When the numbers are scaled tenfold, exhaustive search's steps stay **fixed at 4321**; the table method's steps rise from 37,994 to 377,780, then to 3,775,640. What was added to the input is a **single digit**, and the count of numbers never changed. The conclusion is this: the table method is a polynomial in the target's **value**, not in the number of digits needed to write the target. The space needed to write a number is proportional to its digit count, not its value; this is why input size grows **exponentially** for this method. If input size is read as "count of numbers," the method looks polynomial; if read as "count of digits written," it does not. This lesson defined input size with fixed digit count in CC2, so the first row is honest; once the factor is scaled up, that definition breaks, and the table immediately shows it. ## What Class P Says, What It Does Not Say The two tables above do **not** place the threshold and pair problems in class P. What places them there is not measurement but the **structure of the method**: the threshold method spends exactly n steps on every input, the pair method spends at most n(n-1)/2, and both bounds can be shown without looking at the input. Measurement **tests** this showing; it does not substitute for it. The reverse direction is even stricter. Subset sum requiring 1,048,576 steps at 20 numbers does **not** show that this problem is outside class P. All it shows is that the method built here spends that many steps. Whether another method exists for the same problem was not measured; it was not built in this lesson at all. This course's rule ties this to a single sentence: **an "unsolvable" claim with no stated budget counts as unmeasured.** The engineering counterpart is direct. In a report, the sentence "this problem is solved in polynomial time" needs **that polynomial** and a bound argument alongside it. The sentence "our method finishes in 66 steps on 20 examples" is measured, true, and a much weaker claim. The two are not written in the same sentence. ## Summary - The decision problem class and the growth class are separate things: one groups problems, the other groups a single method's cost expression. - On the same 20 examples the threshold problem is decided in 12 steps, the pair problem in 66; subset sum decides only 7 of 20 examples at a budget of 100 and completes at 10,000. - Raising the budget from 100 to 10,000 changes nothing for the first two problems, and carries the answered example count from 7 to 20 for the third. - As input size rises from 8 to 20, worst-case step counts go from 8 to 20, from 28 to 190, and from 256 to 1,048,576. - An observed step count is not a method's cost: 1047 is observed at 12 numbers but 945 at 16, because the method stops at the first matching subset. - A problem belonging to class P is not shown by measurement; measurement only tests a bound that has already been shown. ## Next Step In the subset sum problem, the scan was expensive, but once the scan finished, one more thing remained: the subset that summed to the target itself. Once that subset is obtained, checking that it is correct does not require redoing the scan. The next lesson turns this observation into a measure: how large is the step gap between **finding** an answer and **verifying** a given one, and what does it mean for this gap to have a class name.