Class NP

The previous lesson scanned the subset sum problem up to 1047 steps at 12 numbers, and once the scan finished, one more thing remained: the subset that summed to the target itself. Once that subset is written down, checking its correctness does not require redoing the scan; a few additions suffice. This lesson turns that observation into a measure.

The difference measured is not a difference in speed; it is two separate costs for two separate questions. The first question: does some subset sum to the target. The second question: does this given subset sum to the target. The method answering the second question performs no search at all; it only looks.

• CC11. A certificate is a witness that makes a “yes” answer verifiable. Here it is a list of indices: which numbers were taken.
• CC12. The verifier is the method that takes a certificate and tests the “yes” answer. A verifier does not search; this is this lesson’s strictest constraint. A verifier that searches is a solver.
• CC13. For the verifier, a step is reading one index; the final comparison also counts as a step. For the solver, a step is one subset.
• CC14. The certificate’s length is measured. A certificate that does not stay proportional to input size does not make verification cheap.
• CC15. The verifier is tested not only by acceptance but also by rejection: what it says when given a corrupted certificate is counted.
• CC16. A certificate is not defined for a “no” answer. This lesson measures only the yes direction; the other direction belongs to lesson 04.
• CC17. The budget sweep is done at four values: 13, 100, 1000, 10,000 steps.
• CC18. Examples come from the shared definition’s generator: seed 20260218, 20 examples, 12 numbers per example. There is no second seed.
• CC19. Whether a problem belongs to class NP is not measured. What is measured is how many steps a specific verifier takes to test a specific certificate.

In Which Sense “Certificate” Is Used

The same word also appears in the Cryptography curriculum, where it names a different thing. The difference fits in one sentence: there, a certificate is a signed document that binds an identity to a public key; here, a certificate is a witness that makes a decision problem’s “yes” answer testable in a short number of steps. The only thing the two share is that both can be verified without being produced by the verifier; beyond that they have no relation and are not used in the same sentence.

NP is a decision problem class: problems whose “yes” answer can be verified with a certificate whose length is a polynomial in input size, and in a polynomial number of steps. The definition contains no mention of “solving.” This is why NP does not mean “not solvable in polynomial time”; the expansion of the name does not say that either.

Every problem in class P is in class NP: if a method exists that can solve a problem in polynomial steps, the verifier can solve the problem from scratch without ever reading the certificate and give the answer. Whether the reverse direction holds is the subject of this course’s lesson 05, and it is open.

Solving Versus Verifying

The block below runs the solver on every example first, takes the certificate it produces, and gives it to the verifier. Then the same certificate, with one index dropped, is given to the verifier again.

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 solver(numbers, target):
    """All subsets are scanned. Returns: (exists, steps, certificate)."""
    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, [i for i in range(n) if mask >> i & 1]
    return False, steps, None


def verifier(numbers, target, certificate):
    """Verifies the given certificate; performs no search at all.
    One step = one index read."""
    steps, total = 0, 0
    for i in certificate:
        steps += 1
        total += numbers[i]
    return total == target, steps + 1


LOG = []
for o in examples():
    exists, steps, cert = solver(o["numbers"], o["target"])
    ok, vs = verifier(o["numbers"], o["target"], cert)
    LOG.append({"example": o, "exists": exists, "solve": steps,
                  "certificate": cert, "verify": vs, "valid": ok})

ts = sum(k["solve"] for k in LOG)
tv = sum(k["verify"] for k in LOG)
print("20 examples, n=12 | yes answer:", sum(1 for k in LOG if k["exists"]), "/ 20")
print("  verifier confirmed certificate:", sum(1 for k in LOG if k["valid"]), "/ 20")
print("  solve steps:", ts, "| verify steps:", tv, "| ratio:", round(ts / tv, 1))
print("  longest certificate:", max(len(k["certificate"]) for k in LOG), "indices")
print()
print("budget  established solving  established with certificate")
for b in (13, 100, 1000, 10000):
    c1 = sum(1 for k in LOG if k["solve"] <= b)
    c2 = sum(1 for k in LOG if k["verify"] <= b)
    print(f"{b:5d}  {c1:14d}  {c2:21d}")
print()
rejected, ra = 0, 0
for k in LOG:
    s = k["certificate"]
    trimmed = s[:-1] if len(s) > 1 else s + [0]
    ok, a = verifier(k["example"]["numbers"], k["example"]["target"], trimmed)
    ra += a
    rejected += not ok
print("certificate with one index dropped | rejected:", rejected, "/ 20",
      "| total steps:", ra)

20 examples, n=12 | yes answer: 20 / 20
  verifier confirmed certificate: 20 / 20
  solve steps: 4321 | verify steps: 101 | ratio: 42.8
  longest certificate: 5 indices

budget  established solving  established with certificate
   13               0                     20
  100               7                     20
 1000              19                     20
10000              20                     20

certificate with one index dropped | rejected: 20 / 20 | total steps: 81

Reading the Three Numbers

Budget 13: with a certificate, 20 of 20 examples are decided; by solving, none. At budget 100, solving rises to 7, at 1000 to 19, at 10,000 to 20. The certificate column, meanwhile, never changes: it was already full at the smallest budget, and growing it found nothing to add. This is the cleanest view of this course’s second claim — raising the budget changes everything in one column and nothing in the other.

The totals say the same thing: solving 4321, verification 101 steps, a ratio of 42.8. The certificate’s length is at most 5 indices; the input has 12 numbers, so the certificate is shorter than the input. Measuring the length is not a formal nicety: the verifier’s step count depends on the certificate’s length, and if a certificate longer than the input were allowed, verification’s cheapness would vanish on its own.

The fourth number shows how serious the verifier is. When one index is dropped from the certificate, the verifier rejects it on 20 of 20 examples, doing so in a total of 81 steps. Rejecting is no more expensive than accepting, but no cheaper either; the verifier only looks either way. Without this measurement, the sentence “verification is cheap” would stay incomplete: a method that approves every certificate is also cheap, and useless.

Why the Certificate’s Shortness Is Part of the Definition

The definition of NP requires the certificate to be polynomial in length. If this condition is dropped, the definition becomes empty, and this can be measured. The block below places three separate certificate designs for the same problem side by side: an index list, only the word “yes,” and the list of all subset sums.

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 short_certificate(numbers, target):
    """Index list. Length at most n."""
    n = len(numbers)
    for mask in range(1 << n):
        if sum(numbers[i] for i in range(n) if mask >> i & 1) == target:
            return [i for i in range(n) if mask >> i & 1]
    return []


def short_verifier(numbers, target, certificate):
    steps, total = 0, 0
    for i in certificate:
        steps += 1
        total += numbers[i]
    return total == target, steps + 1


def empty_verifier(numbers, target, certificate):
    """Certificate is only the word 'yes'; the verifier is forced to search."""
    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 long_certificate(numbers, target):
    """All subset sums are written out in order. Length 2^n."""
    n = len(numbers)
    return [sum(numbers[i] for i in range(n) if m >> i & 1)
            for m in range(1 << n)]


def long_verifier(numbers, target, certificate):
    steps = 0
    for t in certificate:
        steps += 1
        if t == target:
            return True, steps
    return False, steps


EX = examples()
print("certificate      length  verifier steps  budget 13  budget 100  budget 10000")
for name, produce, vf in (("index list    ", short_certificate, short_verifier),
                      ("only 'yes'    ", lambda s, h: [], empty_verifier),
                      ("all sums      ", long_certificate, long_verifier)):
    length = va = 0
    b13 = b100 = b1e4 = 0
    for o in EX:
        cert = produce(o["numbers"], o["target"])
        ok, a = vf(o["numbers"], o["target"], cert)
        length += len(cert)
        va += a
        b13 += a <= 13
        b100 += a <= 100
        b1e4 += a <= 10000
    print(f"{name:15s}  {length:7d}  {va:11d}  {b13:8d}  {b100:9d}  {b1e4:11d}")

certificate      length  verifier steps  budget 13  budget 100  budget 10000
index list            81          101        20         20           20
only 'yes'             0         4321         0          7           20
all sums           81920         4321         0          7           20

The three rows produce the same answer but do three separate jobs. In the first row, total certificate length is 81 indices and the verifier spends 101 steps. In the second row the certificate is empty: since the verifier receives no witness at all, it is forced to search from scratch and spends 4321 steps; this is not a verifier, it is a solver. The third row is sneakier. There is a certificate, in fact a lot of one — 81,920 numbers in total, that is, 4096 per example — and the verifier really does only read, not search. But because what it reads is exponentially longer than the input, the step count is again 4321.

The budget columns close the gap: at budget 13 only the first design gives 20 of 20, the others stay at zero. Without the length bound, a “verifiable” design could be built for every problem, and NP would contain every decision problem. The shortness condition in the definition is what keeps the definition from being empty.

The Advanced Algorithms course had already measured this difference on another problem: in the Hamiltonian path lesson, verifying a candidate path cost 7 steps per graph, finding a path cost 61 on average, and at twelve nodes verification cost 11 steps while showing that no path existed rose to an average of 11,601. That lesson measured the difference and left the naming to here; its name is verifiability, its class is NP.

What the Gap Does with Input Size

The 42.8 ratio over twenty examples is a number taken at a single input size. The second sweep varies input size and places both sides’ worst-case steps side by side. This table runs no examples at all; it computes the two numbers directly, since both can be written without looking at the input.

print(" n  solve (worst case)  verify (worst case)  ratio")
for n in (8, 12, 16, 20, 24):
    print(f"{n:2d}  {1 << n:15d}  {n + 1:19d}  {(1 << n) // (n + 1):9d}")

 n  solve (worst case)  verify (worst case)  ratio
 8              256                    9         28
12             4096                   13        315
16            65536                   17       3855
20          1048576                   21      49932
24         16777216                   25     671088

The left column doubles at every row: 256, 4096, 65,536, 1,048,576, 16,777,216. The middle column rises by one each time: 9, 13, 17, 21, 25. The ratio climbs from 28 to 671,088. As input size triples, the gap grows twenty-four-thousandfold.

The table’s left column carries a warning. The number 16,777,216 is not this problem’s cost; it is this solver’s cost. Whether a method spending fewer steps exists for the same problem was not measured here. The only thing measured is how many subsets exhaustive search sees at 24 numbers. The right column, by contrast, sits closer to the problem itself: given a certificate, n+1 steps suffice, and this bound is independent of which method is chosen.

What Verifiability Does Not Promise

A problem being in class NP does not say the problem is cheap. NP only says this: if the correct answer is “yes,” there exists a short witness that shows it to you. It says nothing about how to find that witness, and this lesson measured that finding it took 4321 steps.

The distinction finds a direct engineering counterpart. In a system, testing that a layout plan, a schedule, or a configuration is valid is often cheap and measurable. Producing that same plan is an entirely different job. Unless a report writes “verification: 13 steps” next to “production: 4096 steps,” the sentence “the system validates the plan” does not say which job was done.

The class name itself carries a warning. NP is short for “nondeterministic polynomial time,” and the nondeterminism here corresponds not to a machine design but to the witness being treated as given. Reading the class name as “not polynomial” is a common mistake, and it inverts every number this lesson measured: the threshold problem, which is in class P, is also in class NP, because the verifier constructs the answer in 13 steps without ever looking at a certificate.

One final limit: no number measured in this lesson proves that subset sum is in class NP. What proves it is the structure of the verifier — the certificate carries at most n indices, and the verifier spends at most n+1 steps, on every input. Measurement tested this structure and found it consistent across 20 examples; this is a test, not a substitute for proof.

Summary

• A certificate is a witness that makes a “yes” answer testable without searching; the verifier reads the certificate, it does not search.
• On the same 20 examples, solving spends 4321 steps, verification 101, a ratio of 42.8; the longest certificate is 5 indices, the input is 12 numbers.
• At a step budget of 13, 20 of 20 examples are decided with a certificate, none by solving; raising the budget to 10,000 changes nothing in the certificate column.
• A certificate with one index dropped is rejected on 20 of 20 examples; the verifier is tested by rejection as much as by acceptance.
• As input size rises from 8 to 24, the worst case for solving goes from 256 to 16,777,216, verification from 9 to 25, and the ratio climbs to 671,088.
• Being in class NP promises no cheapness; it only says a “yes” answer has a short witness, and it says nothing about how to find that witness.

Next Step

This lesson measured a single problem. But most sentences said about difficulty are not about a single problem: they take the form “this problem is at least as hard as that one,” comparing two problems. The next lesson counts how this comparison is built: how many steps the transformation that translates one problem into another takes, whether the transformation preserves the answer, and why translation carries difficulty but does not reduce it.