Class P

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.

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.

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.

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.