--- title: 'Class NP' source: 'https://academia.sh/en/courses/theory-of-computation/class-np' course: 'Theory of Computation' language: en updated: '2026-08-17T18:08:28+00:00' license: 'CC BY-SA 4.0' --- # Class NP Establishing verifiability and the certificate concept in step counts: on 20 examples, solving spends 4321 steps, certificate verification 101, a ratio of 42.8. At a step budget of 13, 20 of 20 examples are decided with a certificate, while solving decides none. At input size 24, solving's worst case is 16,777,216 steps, verification 25. A certificate with one index dropped is rejected on 20 of 20 examples. The difference between this course's sense of "certificate" and the digital certificate sense in the Cryptography curriculum is stated separately. 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. ```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 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. ```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 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. ```python 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.